SP23539 SPLITS - Split

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 $ _{1} $ and S $ _{2} $ . At certain points in time, Petar will be asked to give the string at a given location. He asked you for help.

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 $ _{1} $ S $ _{2} $ ", implying that the fields to the left of X, containing the same string as at X, will from now on have the string S $ _{1} $ , and fields to the right will have the string S $ _{2} $ . A query is represented as "QUERY X", implying that Petar is asked to give the string at location X.

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