L. String Functions

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given two numbers NN, QQ and a string SS of size NN. Followed by Q lines of the following queries:

• pop_back : remove the last character in the string.
• front : print the first character in the string.
• back : print the last character in the string.
• sort l r : where (1l,r|S|)(1l,r|S|) sort all characters of SS from ll to rr.
• reverse l r : where (1l,r|S|)(1l,r|S|) reverse all characters of SS from ll to rr.
• print pos : where (1pos|S|)(1pos|S|) print the character in the index pospos.
• substr l r : where (1l,r|S|)(1l,r|S|) print sub-string of ss from ll to rr.
• push_back x : add character xx in the end of the string.

For each query, print the answer associated with it in a single line.

It's guaranteed that in the first 7 types of the query, the string is not empty.

it's recommended to use built-in functions of String.

Input

The first line contains two integers NN, QQ (1N,Q103)(1N,Q103) NN denoting the size of the string and Q number of queries.

The second line contains the string SS consists of only lowercase English letters.

Next QQ lines contain the queries.

Output

For each query, print the answer associated with it in a single line.