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\)
Initially, A = \(\{ 0, 3, 1, 2 \}\) and LastAns = \(0\)
- Query of 2nd type \(L = 2, R = 3, K = 1\) : LastAns = \(0\)
- Query of 1st type \(X = 1, Y = 2\). Permutation A changed to : \(\{ 3, 0, 1, 2 \}\)
- Query of 2nd type \(L = 2, R = 3, K = 1\) : LastAns = \(2\)
- Query of 2nd type \(L = 1, R = 4, K = 2\) : LastAns = \(5\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor