You are given a permutation $A = \{ a_1, a_2, a_3, ... a_N \}$ of $N$ integers from $0$ to $N-1$.

You are also given $Q$ queries of the following two forms:

• $1~~X~Y$: Swap $(a_X, a_Y)$
• $2~~L~R~K$: Print $MexK$ $(a_L, \ldots, a_R)$

Here, $MexK$$(a_L, \ldots, a_R)$ = $K^{th}$ smallest non-negative integer that is not available in the subarray $(a_L, \ldots, a_R)$.

You can answer the next query only when you answer the previous one. You must answer these queries online.

Input format

• First line: A single integer $N$ denoting the number of elements in the permutation
• Second line: $N$ space-separated integers $a_1, a_2, a_3, ... a_N$
• Next $Q$ lines: Each describing a query

As you are required to respond to the queries online, the queries are encoded.

• A query of the first type is provided in the following format:
  • $1~~X'~Y'$.
• A query of the second type is provided in the following format:
  • $2~~L'~R'~K'$.

You can decode the queries as follows:

$X = X' \oplus LastAns, Y = Y' \oplus LastAns, L = L' \oplus LastAns, R = R' \oplus LastAns, K = K' \oplus LastAns$

Here, $LastAns$ is the last answer to the query of the second type. Initially, $LastAns = 0$.

Output format

For each query, print the answer in a single line

Constraints

$1 \leq N \leq 10^5$

$1 \leq Q \leq 2 * 10^5$

$1 \leq X, Y \leq N$

$1 \leq L \leq R \leq N$

$1 \leq K \leq 10^5$

$0 \leq a_i < N$