시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 13 3 2 40.000%

문제

창영이는 새로운 게임을 만들었다.

이 게임을 하려면 먼저 종이에 양의 정수 N개를 써야 한다. 같은 정수를 두 번 쓸 수 없으며, 1보다 크거나 같고 N보다 작거나 같아야 한다. 이제 연속된 부분 구간을 골라서 왼쪽이나 오른쪽으로 회전시킬 수 있다. (5, 1, 8, 3)을 왼쪽으로 한 번 회전시키면 (1, 8, 3, 5)가 되고, 오른쪽으로 한 번 회전시키면 (3, 5, 1, 8)이 된다. 또, 수열의 특정 위치에 있는 수가 무엇인지 자기 자신에게 물어볼 수도 있다.

즉, 배열은 다음과 같은 세 가지 연산을 수행할 수 있다.

  1. A부터 B까지 구간을 왼쪽으로 K번 회전시킨다. (L a b k)
  2. A부터 B까지 구간을 오른쪽으로 K번 회전시킨다. (R a b k)
  3. X번째 숫자는 무엇일까? (P x)

1번과 2번 연산의 조건은 1 ≤ a < b ≤ N, 1 ≤ k < b-a+1 이며, 3번 연산의 조건은 1 ≤ x ≤ N 이다.

(P x)연산이 주어졌을 때마다 답을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 100,000)과 연산의 개수 Q (1 ≤ Q ≤ 100,000)이 주어진다.

둘째 줄에는 처음 배열에 들어있는 N개의 양의 정수가 주어진다.

다음 Q개 줄에는 문제에 나와있는 형식대로 연산이 하나씩 주어진다.

출력

3번 명령이 주어질 때 마다 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

힌트