Choreography

The Hungarian National Dance Ensemble is practicing a new choreography. There are $N$ dancers numbered from $0$ to $N - 1$, where $N$ is even.

At practice, the choreographer first lines up the dancers. Positions are numbered from $0$ to $N - 1$, and at the start, position $i$ is occupied by dancer $P[i]$.

After the line is formed, the choreographer calls a sequence of moves. Each move finishes before the next one begins. There are four types.

1. Every dancer moves $K$ positions to the right cyclically, where $0 ≤ K < N$. For each $i$ from $0$ to $N-K-1$, the dancer at position $i$ moves to position $i+K$. For each $i$ from $N-K$ to $N-1$, the dancer at position $i$ moves to position $i+K-N$.

2. Every dancer moves $K$ positions to the left cyclically, where $0 ≤ K < N$. For each $i$ from $K$ to $N-1$, the dancer at position $i$ moves to position $i-K$. For each $i$ from $0$ to $K-1$, the dancer at position $i$ moves to position $i-K+N$.

3. For each $i$ from $0$ to $N/2-1$, the dancers at positions $2i$ and $2i+1$ swap places.

4. Suppose position $i$ ($0 ≤ i < N$) is occupied by dancer $r_i$ before this move. For each $j$ from $0$ to $N-1$, dancer $j$ moves to position $r_j$.

The dancers occupy distinct positions after every move.

The choreographer plans a sequence of $M$ moves and adds them one at a time. Before adding the next move, he sometimes asks which position a given dancer occupies after all moves added so far. Simulate the planned moves and answer these questions.

• $1 ≤ N ≤ 100000$
• $0 ≤ P[i] < N$ for each $i$ with $0 ≤ i < N$
• $P[i] ≠ P[j]$ for each $i$ and $j$ with $0 ≤ i < j < N$
• $0 ≤ M ≤ 100000$
• $1 ≤ Q ≤ 200000$
• $0 ≤ K < N$
• $0 ≤ D < N$
• Time limit: 500 ms. Memory limit: 1024 MB.