D. Distributive Property
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a set $$$S$$$ of $$$n$$$ distinct integers. You will also receive $$$q$$$ queries, each of one of the following two types:

  1. Query Type 1 $$$(1\; x)$$$:
    • If $$$x$$$ is currently in the set $$$S$$$, remove it.
    • Otherwise, add $$$x$$$ to the set.
  2. Query Type 2 $$$(2\; t)$$$:
    • Print the cumulative bitwise XOR of $$$(x + t)$$$ over all $$$x \in S$$$. Formally, print $$$\displaystyle\bigoplus_{x \in S} (x + t)$$$.
Input

The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 3 \cdot 10^5$$$) — the initial size of the set and the number of queries, respectively.

The next line of the input will contain $$$n$$$ distinct integers $$$x_1, x_2 \cdots x_n$$$ ($$$0 \le x_i \lt 2^{20}$$$)  — the initial set.

The next $$$q$$$ lines of the input will describe the queries. Each of them will contain a query of the form $$$1\; x$$$ or $$$2\; t$$$ ($$$0 \le x, t \lt 2^{20}$$$), representing the query in the format described above.

It is guaranteed that there is at least one query of type $$$2$$$.

Output

For each query of type $$$2$$$, print the cumulative bitwise XOR of $$$(x+t)$$$ over all $$$x \in S$$$.

Example
Input
3 10
1 6 15
2 0
1 5
1 6
1 10
2 3
2 12
1 15
2 7
1 0
2 7
Output
8
19
17
21
18
Note

In the sample case, at the time of the first type $$$2$$$ query, we have $$$S = \{1, 6, 15\}$$$. Since $$$t = 0$$$ for this query, we print the value $$$$$$(1 + 0) \oplus (6 + 0) \oplus (15 + 0) = 1 \oplus 6 \oplus 15 = 8$$$$$$ At the time of the second type $$$2$$$ query, we have $$$S = \{1, 5, 10, 15\}$$$. Since $$$t = 3$$$ for this query, we print the value $$$$$$(1 + 3) \oplus (5 + 3) \oplus (10 + 3) \oplus (15 + 3) = 4 \oplus 8 \oplus 13 \oplus 18 = 19$$$$$$