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\)