I was just searching some stuff related to CF users, and I accidentally found a feature , about which I didn't know as a 3 years user of Codeforces. In short, you can create a list of users (who are interesting for you), and easily track their problem solving activity during the rounds, in the problemset, etc. You can find the "LISTS" feature in your profile page.

I guess a lot of people never heard about this, so i wanted to share with you.

Read more about the feature here

It would be good if before the start of the competition, besides the number of registered users, the number of registered online users would also be available. This will help to understand the real number of participants.

Please help me to solve this problem.

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).