Background

This problem is the enhanced testdata version of P3369. It expands the constraints and adds forced online.

The input and output of this problem are slightly different from the original one, but the operations that need to be supported are the same.

Problem 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