Permutation Cycles and Queries

You are given an array $A$ of $n$ distinct integers from $1$ to $n$, and an integer $m$. Define $S^0(i)=i$ and $S^k(i)=A[S^{k-1}(i)]$ for $1 \le k \le m$ and $1 \le i \le n$. There is a list $Q$ of $q$ queries about $S^m(i)$. Each query is one of two types.

• Type 1, 1 i j: swap the values of $A[i]$ and $A[j]$.
• Type 2, 2: print $S^m(1) \times 1 + S^m(2) \times 2 + \cdots + S^m(n) \times n$.

Process the queries in $Q$ in order, from the first to the $q$-th, and print the result of each type 2 query.

The first line contains $n$ and $m$, separated by a space.

The second line contains the elements $A[1], A[2], \ldots, A[n]$, separated by spaces.

The third line contains the number of queries $q$.

The next $q$ lines each contain one query as a sequence of integers separated by spaces.

For each type 2 query, print the result on its own line, in the order the queries appear.

• $1 \le n, q \le 100{,}000$
• $1 \le m \le 10^{1{,}000}-1$
• $1 \le A[i] \ne A[j] \le n$ for $1 \le i \ne j \le n$
• Every query in $Q$ is type 1 or type 2.
• $Q$ contains at least 1 and at most $\min(q, 1{,}000)$ type 2 queries.

$S^m$ is the result of applying the move operation to the elements of array $A$ exactly $m$ times. Let $S^k(i)$ be the position of the $i$-th element after $k$ moves, so the initial position is $S^0(i)=i$, the position after one move is $S^1(i)=A[i]$, and after $m$ moves it is $S^m(i)=A[S^{m-1}(i)]$.

For example, let $A=\{2, 1, 3\}$ and $m=3$. For the first element, $S^0(1)=1$, $S^1(1)=A[1]=2$, $S^2(1)=A[S^1(1)]=1$, and $S^3(1)=A[S^2(1)]=2$. For the second element, $S^0(2)=2$, $S^1(2)=A[2]=1$, $S^2(2)=A[S^1(2)]=2$, and $S^3(2)=A[S^2(2)]=1$. For the third element, $S^k(3)=3$ for every $k$.