안무

시간 제한0.5초메모리 제한1024 MB

요약

N명의 무용수가 줄을 선 상태에서 순환 이동, 쌍 교환, 임의 치환 동작을 차례로 적용합니다. 각 동작 뒤에 특정 무용수의 위치를 구합니다.

문제

헝가리 국립무용단이 새 안무를 연습하고 있다. 무용수는 $N$ 명이며 0부터 $N-1$ 까지 번호가 붙어 있다. $N$ 은 짝수이다.

연습에서 안무가는 먼저 무용수를 한 줄로 세운다. 위치는 0부터 $N-1$ 까지 번호가 붙어 있고, 처음에는 위치 $i$ 에 무용수 $P[i]$ 가 선다.

줄을 세운 뒤 안무가는 동작을 차례로 지시한다. 각 동작이 끝나야 다음 동작을 시작한다. 동작은 네 종류이다.

모든 무용수가 오른쪽으로 $K$ 칸 순환 이동한다. 여기서 $0 ≤ K < N$ 이다. $0$ 부터 $N-K-1$ 까지의 각 $i$ 에 대해 위치 $i$ 의 무용수는 위치 $i+K$ 로 간다. $N-K$ 부터 $N-1$ 까지의 각 $i$ 에 대해 위치 $i$ 의 무용수는 위치 $i+K-N$ 으로 간다.
모든 무용수가 왼쪽으로 $K$ 칸 순환 이동한다. 여기서 $0 ≤ K < N$ 이다. $K$ 부터 $N-1$ 까지의 각 $i$ 에 대해 위치 $i$ 의 무용수는 위치 $i-K$ 로 간다. $0$ 부터 $K-1$ 까지의 각 $i$ 에 대해 위치 $i$ 의 무용수는 위치 $i-K+N$ 으로 간다.
$0$ 부터 $N/2-1$ 까지의 각 $i$ 에 대해 위치 $2i$ 와 $2i+1$ 의 무용수가 자리를 바꾼다.
이 동작 전에 위치 $i$ ( $0 ≤ i < N$ )에 무용수 $r_i$ 가 서 있다고 하자. $0$ 부터 $N-1$ 까지의 각 $j$ 에 대해 무용수 $j$ 는 위치 $r_j$ 로 간다.

모든 동작이 끝난 뒤에도 무용수들의 위치는 서로 다르다.

안무가는 $M$ 개의 동작으로 이루어진 계획을 세우고, 동작을 하나씩 추가한다. 다음 동작을 추가하기 전에, 지금까지 추가한 모든 동작을 수행한 뒤 특정 무용수가 어느 위치에 있는지 묻기도 한다. 계획된 동작을 시뮬레이션하고 이 질문들에 답하라.