Strings are like plants in that they require a lot of loving care to grow. In this problem we will follow the evolution of a garden with N strings during a period covering T seasons. The strings in the garden are numbered from 1 to N, and are all initially empty. Each season we will perform two tasks in our garden:

• At the beginning of the season, we may prune the garden by deleting the C characters on the rightmost end of each of the N strings in the garden.
• After the pruning is done, we fertilize the garden so that each of the N strings grows by appending one character (possibly different for each string) to its rightmost end.

At the end of the season, a good string gardener always takes a moment to contemplate his/her work. In order to do this, we take a number P from 1 to N and then dedicate ourselves to appreciate the beauty of the string that stands at position P when we sort the N strings in the garden alphabetically from smallest to largest (breaking draws arbitrarily by putting first the strings identified with smaller numbers).

These moments of contemplation should be a well-deserved resting time for the gardener, so we don't want to waste time sorting the strings in the garden to identify the one we want to appreciate. Can you help us find it?

Input

The first line contains two integer numbers N and T, representing the number of strings in the garden and the number of seasons we follow their evolution, respectively (2 ≤ N ≤ 100 and 1 ≤ T ≤ 10⁴). The following T lines describe one season each, in the same order in which they take place.

The description of each season consists of a number C, a string S and another number P (1 ≤ P ≤ N). The number C is non-negative and represents the number of characters that are deleted during the pruning period at the beginning of the corresponding season (so it can be zero in case that no pruning is performed in that season). The string S contains exactly N characters s₁, s₂, ..., s_N, being the i-th character s_i the one that should be appended to the rightmost end of the string identified by the number i (s_i is a lower-case letter of the English alphabet for i = 1, 2, ..., N). Finally, the number P represents the position of the string we would like to appreciate at the end of the season, when we sort the N strings in the garden as explained in the problem statement.

Output

Print T lines, one for each season described in the input. The i-th line should contain the number identifying the string we want to appreciate at the end of the i-th season, for i = 1, 2, ..., T.

Example 1

Input:
2 4
0 aa 1
0 ba 1
1 ba 2
2 aa 2

Output:
1
2
1
2

Example 2

Input:
26 26
0 abcdefghijklmnopqrstuvwxyz 1
1 bcdefghijklmnopqrstuvwxyza 2
1 cdefghijklmnopqrstuvwxyzab 3
1 defghijklmnopqrstuvwxyzabc 4
1 efghijklmnopqrstuvwxyzabcd 5
1 fghijklmnopqrstuvwxyzabcde 6
1 ghijklmnopqrstuvwxyzabcdef 7
1 hijklmnopqrstuvwxyzabcdefg 8
1 ijklmnopqrstuvwxyzabcdefgh 9
1 jklmnopqrstuvwxyzabcdefghi 10
1 klmnopqrstuvwxyzabcdefghij 11
1 lmnopqrstuvwxyzabcdefghijk 12
1 mnopqrstuvwxyzabcdefghijkl 13
1 nopqrstuvwxyzabcdefghijklm 14
1 opqrstuvwxyzabcdefghijklmn 15
1 pqrstuvwxyzabcdefghijklmno 16
1 qrstuvwxyzabcdefghijklmnop 17
1 rstuvwxyzabcdefghijklmnopq 18
1 stuvwxyzabcdefghijklmnopqr 19
1 tuvwxyzabcdefghijklmnopqrs 20
1 uvwxyzabcdefghijklmnopqrst 21
1 vwxyzabcdefghijklmnopqrstu 22
1 wxyzabcdefghijklmnopqrstuv 23
1 xyzabcdefghijklmnopqrstuvw 24
1 yzabcdefghijklmnopqrstuvwx 25
1 zabcdefghijklmnopqrstuvwxy 26

Output:
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1