XOR Queries

The array $A$ is empty at the start. Process the following five kinds of queries in the order they are given. Array indices start at 1.

• 1 x: append $x$ to the end of $A$.
• 2 L R x: among the $L$-th through $R$-th elements of $A$, print the element $y$ whose xor with $x$ is largest. Two different values give two different xor results, so this $y$ is unique.
• 3 k: remove the last $k$ elements of $A$.
• 4 L R x: print how many of the $L$-th through $R$-th elements of $A$ are less than or equal to $x$.
• 5 L R k: print the $k$-th smallest number among the $L$-th through $R$-th elements of $A$. A value that occurs several times is counted once per occurrence.

The first line contains the number of queries $M$ ($1 \le M \le 500{,}000$).

Each of the next $M$ lines contains one query. In queries of type 1, 2 and 4, the value $x$ satisfies $1 \le x \le 500{,}000$.

Let $N$ be the length of $A$ right before a query runs. Queries of type 2, 4 and 5 satisfy $1 \le L \le R \le N$, and a query of type 3 satisfies $1 \le k \le N$. A query of type 5 also satisfies $k \le R-L+1$.

For every query of type 2, 4 and 5, print its answer on its own line, in the order the queries are given.