Description

You need to dynamically maintain a multiset $M$, and provide the following operations:

1. Insert a number $x$ into $M$.
2. Delete a number $x$ from $M$ (if there are multiple identical numbers, delete only one).
3. Query how many numbers in $M$ are less than $x$, and then add $1$ to the result.
4. Query the number whose rank is the $x$-th when $M$ is sorted in increasing order.
5. Query the predecessor of $x$ in $M$ (the predecessor is defined as the largest number less than $x$).
6. Query the successor of $x$ in $M$ (the successor is defined as the smallest number greater than $x$).

This problem is forced online. All operations are guaranteed to be valid (for operation $2$, there is guaranteed to be at least one $x$; for operations $4,5,6$, an answer is guaranteed to exist).

Input Format

The first line contains two positive integers $n,m$, representing the number of initial numbers and the number of operations.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$, representing the initial numbers.

Next there are $m$ lines, each containing two integers $\text{opt}$ and $x'$. $\text{opt}$ indicates the operation index ($1 \leq \text{opt} \leq 6$), and $x'$ indicates the encrypted operand.

Let $\text{last}$ denote the answer of the most recent operation among $3,4,5,6$. Then in each operation, the real $x$ is obtained by XORing $x'$ with $\text{last}$. Initially, $\text{last}=0$.

Output Format

Output one line with one integer, representing the XOR sum of the answers of all operations $3,4,5,6$.

6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4

6

Hint

Sample Explanation

Before encryption, the sample is:

6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 9
3 8
6 1
1 0

::::info[Output of each operation] Before the first operation, $M=\{1,1,1,4,4,5\}$. After it, $M=\{1,1,4,4,5\}$.

After the second operation, $M=\{1,1,4,4,5,9\}$.

The third operation queries the $1$-st smallest number in $M$, and the answer is $1$.

The fourth operation queries the predecessor of $9$ in $M$, and the answer is $5$.

The fifth operation queries how many numbers in $M$ are less than $8$, and then adds $1$ to the result. The answer is $6$.

The sixth operation queries the successor of $1$ in $M$, and the answer is $4$.

After the seventh operation, $M=\{0,1,1,4,4,5,9\}$.

The output is $1\oplus5\oplus6\oplus4=6$. ::::

Limits and Notes

For $100\%$ of the testdata, $1\leq n\leq 10^5$, $1\leq m\leq 10^6$, $0\leq a_i,x\lt 2^{30}$.

The input size of this problem is large. Please use a fast input method.

$\text{upd 2022.7.22}$: Added $9$ new sets of hack testdata.

Translated by ChatGPT 5