Micro just bought a new game called Strings. The game consists of an array of N strings. and Q operations. Each operation can be one of the following two types:
1. 0 x y c : Change yth character of xth string in the array to c. Consider 1-based indexing of characters in the string as well as of the strings in the array.
2. 1 x : Make a lexicographically sorted set of strings out of the array of strings and tell the string at the xth position in that set.
A player wins the game if he can perform all the operations correctly. Help Micro win the game.
Input:
First line consists of two space separated integers denoting N and Q.
Second line consists of N strings separated by space. Then
Q lines follow each containing an operation as defined above.
Output:
For each operation of type 2 print, in a new line, the string which appears at the xth position in the sorted set of strings.
Constraints:
1 ≤ N ≤ 105
1 ≤ Q ≤ 106
1 ≤ Length of strings in array ≤ 10
All the strings are made of lower case characters. It is assured that all the operations are valid.
Set of strings made by the given array of strings is { "abcd" }. So clearly string at 1st position in set is "abcd".
Second query update the second string to "aacd".
Third query update the second string to "aaad".
Now the array looks like : "abcd", "aaad", "abcd", "abcd". And the sorted set of strings looks like {"aaad", "abcd"}. So string at 1st position is "aaad" and at 2nd position is "abcd".
