beecrowd | 2843

Fast Writing, the Competition

By Gustavo Policarpo, INATEL BR Brazil

Timelimit: 1

Matheus and his twin brother Vinicius have decided to expand their tying duel to a major competition in which key players from many parts of the world take part.
The competition takes place in several phases and in each one the participants are placed in a row ordered by their respective indexes and the ith participant will duel with the ith + 1, and the winner advances to the next phase. In case of a tie, the lowest index participant passes. He is declared winner of a duel, the one that can enter a certain phrase faster, that is, the one that obtains the less time resulting from its reaction time added to the time necessary to enter the phrase of that round. In each phase also, the text used will be the previous one concatenated with itself.
Given each competitor's information, please tell us which stage each will reach.

Input

The first line of the entry consists of an integer N representing the number of participants. The next N lines consist of two integers Ri and Ei representing the reaction time and the writing time, that is, the time it takes to type each character regardless of which is, in milliseconds of the i-th participant. The last line consists of the text S used in the first phase of the competition. It is guaranteed that following the rules of the competition all phases will be an even number of participants, except for the last, and that the text S contains only alphanumeric characters, punctuation marks and spaces.

1 ≤ N ≤ 65536

1 ≤ Ri, Ei ≤ 1000

1 ≤ |S| ≤ 100000

Output

The output should be a line containing the phase number in which each participant arrives.

Input Samples Output Samples

4

4 1

3 1

2 1

1 1

ABCD

1 2 1 3

2

5 2

23 1

leibe do biruleibe

2 1

In the first example: In phase 1 the first participant hurts with the second, and the third with the fourth on the text ABCD. Each participant takes, respectively, 8, 7, 6, 5 milliseconds to complete the challenge, advancing then the second and fourth participant. In phase 2, we have the duel of the second and fourth participant, ABCDABCD text, which they spend respectively 11 and 9 milliseconds, advancing the fourth participant.