Little Petar has been put in charge of maintaining an unpredictable array of strings. Initially, all of the array elements were the same string S, but the array is prone to change; and there is exactly one kind of change that may happen. This is a split operation at a given location, X; after it is performed, the location X maintains the string it had before, however all fields to the left and all fields to the right of X containing the same string as X will be given new strings, S₁ and S₂.

At certain points in time, Petar will be asked to give the string at a given location. He asked you for help.

Input

The first line of the standard input contains two numbers, N and Q, the size of the array and the total number of operations and queries, respectively.

The second line contains the string S, the string initially contained within each location of the array.

The following Q lines contain the description of either an operation or a query:

A split operation is represented as "SPLIT X S₁ S₂", implying that the fields to the left of X, containing the same string as at X, will from now on have the string S₁, and fields to the right will have the string S₂.

A query is represented as "QUERY X", implying that Petar is asked to give the string at location X.

Output

For each QUERY command given, output a new line containing the string currently located on the given position.

Example

Input:
6 6
picsel
SPLIT 3 petarv duxserbia
SPLIT 5 sasav nikolaj
QUERY 1
QUERY 3
QUERY 5
QUERY 6

Output:
petarv
picsel
duxserbia
nikolaj

Explanation

Initially, the string picsel is located throughout the array. After the first and second split operation, respectively, the array looks as follows:

[petarv, petarv, picsel, duxserbia, duxserbia, duxserbia]

[petarv, petarv, picsel, sasav, duxserbia, nikolaj]

The answers to the queries then clearly follow from the final state of the array.

Constraints

• 1 <= N, Q <= 10⁵
• 1 <= X <= N
• 1 <= |S|, |S₁|, |S₂| <= 50
• The strings will consist solely of lowercase letters of the English alphabet.
• All strings appearing in the operations will be unique.