TAP2014F  String fertilization
[ The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014problems.pdf ]
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 welldeserved 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^{4}). 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 nonnegative 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_{1}, s_{2}, ..., s_{N}, being the ith 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 lowercase 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 ith line should contain the number identifying the string we want to appreciate at the end of the ith 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
hide comments
:D:
20141005 00:48:19
Problem can be solved optimally in respect to input data size. Additionally memory complexity required is pretty low. Last edit: 20181018 12:41:18 

mehmetin:
20141004 16:11:27
can you tell something about the expected complexity? Couldn't solve it... Last edit: 20160310 18:11:25 
Added by:  Fidel Schaposnik 
Date:  20140929 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Argentinian Programming Tournament 2014 