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 already in the set.
• Operation 2: Given $x$, delete an element $x$. It is guaranteed that $x$ is currently in the set.

After each operation, you need to output $\max\limits_{\substack{ i, j \in S \\ i \ne j }} \bigl( (i+j) \bmod C \bigr)$, which is the maximum value of the sum of two distinct elements in $S$ modulo $C$. If there are fewer than two elements in $S$, output EE.

This problem is forced online. Each $x$ must be XORed with the answer of the previous operation. If there was no previous query or the previous output was EE, the previous answer is $0$.

Input

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

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

Output

Output $n$ lines, where the $i$-th line represents the answer after the $i$-th operation.

Examples

Input 1

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

Output 1

EE
5
8
8
8
5
7

Subtasks

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

Note: This problem uses bundled testing. You only receive points for a subtask if you pass all test cases within that subtask.

For $1\%$ of the data, it is Example 1.

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

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

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

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

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