순열 사이클과 쿼리

1 이상 $n$ 이하의 서로 다른 정수 $n$개로 이루어진 배열 $A$와 정수 $m$이 주어진다. $S^0(i)=i$, $S^k(i)=A[S^{k-1}(i)]$ ($1 \le k \le m$, $1 \le i \le n$)로 정의한다. $S^m(i)$에 대한 $q$개의 질의가 질의 목록 $Q$에 저장되어 있다. 질의는 두 가지 유형이다.

• 유형 1 1 i j: $A[i]$와 $A[j]$의 값을 교환한다.
• 유형 2 2: $S^m(1) \times 1 + S^m(2) \times 2 + \cdots + S^m(n) \times n$을 출력한다.

$Q$의 첫 번째 질의부터 $q$번째 질의까지 순서대로 처리하면서 유형 2 질의의 결과를 출력한다.

첫 번째 줄에 $n$과 $m$이 공백으로 구분되어 주어진다.

두 번째 줄에 배열 $A$의 원소 $A[1], A[2], \ldots, A[n]$이 공백으로 구분되어 주어진다.

세 번째 줄에 질의의 수 $q$가 주어진다.

네 번째 줄부터 $q$개의 줄에 걸쳐 질의 목록 $Q$의 질의가 순서대로 주어진다. 한 줄에 질의 하나를 나타내는 정수가 공백으로 구분되어 있다.

유형 2 질의의 결과를 질의 순서대로 한 줄에 하나씩 출력한다.

• $1 \le n, q \le 100{,}000$
• $1 \le m \le 10^{1{,}000}-1$
• $1 \le A[i] \ne A[j] \le n$ ($1 \le i \ne j \le n$)
• $Q$에 저장된 질의는 유형 1과 유형 2뿐이다.
• $Q$에 저장된 유형 2 질의는 1개 이상 $\min(q, 1{,}000)$개 이하이다.

$S^m$은 배열 $A$의 원소를 이동시키는 연산을 $m$번 반복하는 동작이다. $i$번째 원소에 이동 연산을 $k$번($0 \le k \le m$) 수행한 후의 위치를 $S^k(i)$라고 하자. 초기 위치는 $S^0(i)=i$이고, 1번 이동한 후의 위치는 $S^1(i)=A[i]$이며, $m$번 이동한 후의 위치는 $S^m(i)=A[S^{m-1}(i)]$이다.

예를 들어 $A=\{2, 1, 3\}$이고 $m=3$이라고 하자. 첫 번째 원소는 $S^0(1)=1$, $S^1(1)=A[1]=2$, $S^2(1)=A[S^1(1)]=1$, $S^3(1)=A[S^2(1)]=2$로 이동한다. 두 번째 원소는 $S^0(2)=2$, $S^1(2)=A[2]=1$, $S^2(2)=A[S^1(2)]=2$, $S^3(2)=A[S^2(2)]=1$로 이동한다. 세 번째 원소는 모든 $k$에 대해 $S^k(3)=3$이다.