Given a permutation of 1,2...,N numbers. There are 3 types of queries.

1. perform K times cyclic shift of the segment [l,r] to the right.

2. perform K times cyclic shift of the segment [l,r] to the left.

3. Print which number is at position X in current array.

Size of array N (2 ≤ N ≤ 100 000). Number of queries Q (1 ≤ Q ≤ 100 000).