Background

Uh... me.

The input size of this problem is about 6 MB, and the output size is about 5 MB. Please choose appropriate input/output methods.

Problem Description

Given a constant $C$, you need to maintain a set $S$ and support $n$ operations:

• Operation 1: given $x$, insert an element $x$. It is guaranteed that $x$ is not in the set before this operation.
• Operation 2: given $x$, delete an element $x$. It is guaranteed that $x$ is in the set before this operation.

After each operation, output $\max\limits_{\substack{ i, j \in S \\ i \ne j }} \bigl( (i+j) \bmod C \bigr)$, that is, choose two different elements from $S$ and take the maximum value of their sum $\bmod~C$. If there are fewer than two elements in $S$, output EE.

This problem is strictly online. Each $x$ must be $\operatorname{xor}$-ed with the previous answer. If there was no previous query or the output was EE, then the previous answer is $0$.

Input Format

The first line contains two integers $n, C$.

The next $n$ lines each contain two integers $1~x$ or $2~x$, representing an operation of type 1 or type 2.

Output Format

Output $n$ lines. The $i$-th line is the answer after the $i$-th operation.

7 9
1 2
1 3
1 0
1 14
2 14
2 13
1 1

EE
5
8
8
8
5
7

Hint

Idea: zhouwc, Solution: ccz181078&nzhtl1477, Code: ccz181078&nzhtl1477, Data: nzhtl1477.

Note: This problem uses bundled tests. You can get the score of a subtask only after passing all test points in that subtask.

For $1\%$ of the testdata, it is Sample 1.

For another $9\%$ of the testdata, the number of elements in the set is $\le 1$.

For another $19\%$ of the testdata, $n \leq 500$.

For another $19\%$ of the testdata, $n \leq 10^4$.

For another $19\%$ of the testdata, $1 \leq n,C \leq 10^5$.

For $100\%$ of the testdata, $1 \leq n \leq 5\times 10^5$, $1 \leq C \leq 1073741823$, $0 \leq x \leq 1073741823$.

Translated by ChatGPT 5