RINGIŠPIL

문제

Mirko wanted to spin on a spinner today, but outside pretty bad rain started and he decided to stay in his house. Therefore, he invented new game which he intended to play whole day. 

First, on one piece of paper he wrote N different positive integers between 1 and N. Now, he can choose any interval of subsequent elements and rotate it left or right. Example, if (5, 1, 8, 3) is the interval, then after one left rotation he gets (1, 8, 3, 5). Similar, with one right rotation he gets (3, 5, 1, 8). Beside rotating choosen intervals, Mirko can ask him self which number is on specific position. 

So, there are three diferent operation on the array: 

1. Interval from position A to B Mirko rotates K times to the left. Operation: L a b k 
2. Interval from position A to B Mirko rotates K times to the right. Operation: R a b k 
3. Mirko ask him self which number is at position X in current array. Operation: P x 

For 1. and 2. operation constraints are 1 ≤ a < b ≤ N, te 1 ≤ k < b – a + 1. 

For 3. operation constraint is 1 ≤ x ≤ N. 

Help Mirko and ask for him which number is at position X for every operation P x. 

입력

The first line of input contains two positive integers N (2 ≤ N ≤ 100 000) and Q (1 ≤ Q ≤ 100 000), size of array na number of operations. 

Second line of input contains N positive integers. This line represents array at the begining of the game. 

Next Q lines represent operations in described format. 

출력

For every 3. command (P x) write single integer on a line which represents which number is at position x.

7 5
7 5 3 1 4 2 6
L 1 3 2
R 2 4 1
P 1
P 4
P 7

3
5
6

5 5
3 5 4 2 1
R 3 5 1
R 1 4 1
P 1
R 1 5 4
P 1

4
3