안무

헝가리 국립 무용단은 새로운 안무를 연습하고 있다. 무용단에는 $0$부터 $N-1$까지 번호가 매겨진 $N$명의 무용수가 있으며, $N$은 짝수이다.

연습 시간에 안무가는 먼저 무용수들을 한 줄로 세운다. 줄의 위치에는 $0$부터 $N-1$까지 번호가 매겨져 있으며, 처음에 위치 $i$는 무용수 $P[i]$가 차지한다.

무용수들이 줄을 선 뒤, 안무가는 그들에게 일련의 동작을 수행하도록 지시한다. 각 동작은 다음 동작을 시작하기 전에 완료되어야 한다. 무용수들은 다음 4가지 유형의 동작을 연습한다.

1. 모든 무용수가 오른쪽으로 $K$칸씩 순환하여 이동한다. 여기서 $0 \le K < N$이다. 즉,
   • $0$부터 $N-K-1$까지의 각 $i$에 대해, 현재 위치 $i$에 서 있는 무용수는 위치 $i+K$로 이동하고,
   • $N-K$부터 $N-1$까지의 각 $i$에 대해, 현재 위치 $i$에 서 있는 무용수는 위치 $i+K-N$으로 이동한다.
2. 모든 무용수가 왼쪽으로 $K$칸씩 순환하여 이동한다. 여기서 $0 \le K < N$이다. 즉,
   • $K$부터 $N-1$까지의 각 $i$에 대해, 현재 위치 $i$에 서 있는 무용수는 위치 $i-K$로 이동하고,
   • $0$부터 $K-1$까지의 각 $i$에 대해, 현재 위치 $i$에 서 있는 무용수는 위치 $i-K+N$으로 이동한다.
3. $0$부터 $\frac{N}{2}-1$까지의 각 $i$에 대해, 위치 $2i$와 $2i+1$에 있는 무용수들이 서로 자리를 바꾼다.
4. 이 동작을 수행하기 전에 위치 $i$ ($0 \le i < N$)를 무용수 $r_i$가 차지하고 있다고 하자. $0$부터 $N-1$까지의 각 $j$에 대해, 무용수 $j$는 위치 $r_j$로 이동한다.

각 동작이 끝났을 때 무용수들의 위치는 서로 다르다는 점에 유의하라.

다음 연습 전에 안무가는 무용단이 연습할 $M$개의 동작으로 이루어진 수열을 계획한다. 그는 동작을 수열에 하나씩 추가한다. 때때로 다음 동작을 추가하기 전에, 지금까지 수열에 추가된 모든 동작을 수행한 직후 특정 무용수들이 어느 위치를 차지할지 궁금해한다.

여러분의 과제는 안무가가 계획한 무용 동작을 시뮬레이션하고 무용수들의 위치에 관한 그의 질문에 답하는 것이다.

구현 세부사항

다음 프로시저를 구현해야 한다.

void init(int N, int[] P)

• $N$: 무용수의 수.
• $P$: 무용수들의 초기 순서를 나타내는 길이 $N$의 배열.
• 이 프로시저는 다른 모든 함수 호출보다 먼저 정확히 한 번 호출된다.

void move_right(int K)

• $K$: 각 무용수가 오른쪽으로 이동하는 위치의 수.
• 이 프로시저는 동작 수열에 유형 1의 동작을 추가한다.

void move_left(int K)

• $K$: 각 무용수가 왼쪽으로 이동하는 위치의 수.
• 이 프로시저는 동작 수열에 유형 2의 동작을 추가한다.

void swap_places()

• 이 프로시저는 동작 수열에 유형 3의 동작을 추가한다.

void move_around()

• 이 프로시저는 동작 수열에 유형 4의 동작을 추가한다.

프로시저 move_right, move_left, swap_places, move_around는 합계 $M$번 호출된다.

int get_position(int D)

• $D$: 무용수를 나타내는 정수.
• 이 프로시저는 이 호출 전에 동작 수열에 추가된 모든 동작을 수행한 뒤 무용수 $D$가 있는 위치를 반환해야 한다.
• 이 프로시저는 $Q$번 호출된다.

예제

다음과 같은 호출 수열을 생각해 보자.

init(6, [5, 1, 4, 2, 0, 3])

무용수는 6명이고, 무용수들의 초기 순서는 배열 $[5,1,4,2,0,3]$으로 주어진다. 즉, 위치 0은 무용수 5가 차지하고, 위치 1은 무용수 1이 차지하며, 위치 2는 무용수 4가 차지하는 식이다.

move_left(2)

각 무용수가 왼쪽으로 두 칸씩 순환하여 이동한다. 이 동작 후 무용수들의 순서는 $[4,2,0,3,5,1]$이 된다.

get_position(0)

이 호출은 첫 번째 동작을 수행한 뒤 무용수 0의 위치를 묻는다. 무용수 0은 위치 2에 서 있다. 따라서 프로시저는 2를 반환해야 한다.

swap_places()

이 동작 후 무용수들의 순서는 $[2,4,3,0,1,5]$가 된다.

move_around()

각 무용수의 새로운 위치는 다음과 같이 결정된다.

• 무용수 0: 위치 0은 무용수 2가 차지하므로, 무용수 0은 위치 2로 이동한다.
• 무용수 1: 위치 1은 무용수 4가 차지하므로, 무용수 1은 위치 4에 그대로 있는다.
• 무용수 2: 위치 2는 무용수 3이 차지하므로, 무용수 2는 위치 3으로 이동한다.
• 무용수 3: 위치 3은 무용수 0이 차지하므로, 무용수 3은 위치 0으로 이동한다.
• 무용수 4: 위치 4는 무용수 1이 차지하므로, 무용수 4는 위치 1에 그대로 있는다.
• 무용수 5: 위치 5는 무용수 5가 차지하므로, 무용수 5는 위치 5에 그대로 있는다.

이 동작 후 무용수들의 순서는 $[3,4,0,2,1,5]$가 된다.

get_position(3)

지금까지의 모든 동작을 수행한 뒤 무용수 3은 위치 0에 있다. 프로시저는 0을 반환해야 한다.

제약 조건

• $1 \le N \le 100\,000$
• $0 \le P[i] < N$ ($0 \le i < N$인 각 $i$에 대해)
• $P[i] \ne P[j]$ ($0 \le i < j < N$인 각 $i$와 $j$에 대해)
• $0 \le M \le 100\,000$
• $1 \le Q \le 200\,000$
• $0 \le K < N$
• $0 \le D < N$

서브태스크

1. (7점) 유형 1과 2의 동작만 수행된다.
2. (12점) $N \cdot (Q+M) \le 1\,000\,000$
3. (10점) 유형 4의 동작만 수행된다.
4. (14점) 유형 3과 4의 동작만 수행된다.
5. (28점) 유형 1, 2, 4의 동작만 수행된다.
6. (29점) 추가 제약 조건이 없다.

샘플 그레이더는 다음 형식으로 입력을 읽는다.

• 1번째 줄: $N\ M\ Q$
• 2번째 줄: $P[0]\ P[1]\ \ldots\ P[N-1]$
• $3+l$번째 줄 ($0 \le l < M+Q$):
  • 유형 1의 동작을 수행하려면: 1 K
  • 유형 2의 동작을 수행하려면: 2 K
  • 유형 3의 동작을 수행하려면: 3
  • 유형 4의 동작을 수행하려면: 4
  • 무용수의 위치를 물으려면: 5 D

샘플 그레이더는 다음 형식으로 여러분의 답을 출력한다.

• $1+q$번째 줄 ($0 \le q < Q$): get_position이 반환한 값