SP21173 TAP2014F - String fertilization

**\[ The original version of this problem (in Spanish) can be found at [http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf](http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf "http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.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 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? 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:

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 ****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 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 $ _{1} $ , s $ _{2} $ , ..., 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.****

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**.