URI Online Judge | 2529

Flea Circus

By Flávio Zavan, UFPR BR Brazil

Timelimit: 2

Vasya and Petya decided to invest in a new enterprise. They opened a flea circus.

Right now, they are rehearsing with their P fleas in a straight line. Each flea holds a small board with an integer written on it, and can follow 4 different orders:

Some fleas did not understand the last order and asked for an example. Vasya then said:

Consider there are 10 fleas holding, initially, boards with the following integers:

70, 15, 3, 4, 15, 59, 0, 1, 444, 2

If they receive the order to reverse the order of the boards in the interval [3, 7], then the new line will be:

70, 15, 0, 59, 15, 4, 3, 1, 444, 2

The duo asked you to write a program to simulate the rehearsing, so they can see if they are well trained.

Input

The input contains several test cases. In each test case, the first line contains two integers P and Q (1 ≤ P, Q ≤ 105). The following line contains P integers pi (0 ≤ pi ≤ 109), the integers initially written on the fleas’ boards.

Next Q lines describe the orders they receive. Each order may be:

The input ends with end-of-file (EOF).

Output

For each test case, print a line with the value that must be yelled for each order that requires an yell (E and O).

Input Sample Output Sample

7 8
30 50 1 2 3 4 10
O 1 7
S 2 7
E 1 7
S 3 8
O 1 7
O 1 3
I 3 5
O 1 3

2
4
2
1
2