Given a multiset ~S~ of ~n~ non-negative integers. Perform ~q~ queries of one of the following three types:

• ~\mathtt{1\;} x~: Add ~x~ to ~S~.

• ~\mathtt{2\;} x~: Remove one occurrence of ~x~ from ~S~.

• ~\mathtt{3\;} k~: Among all ways to partition ~S~ into ~k~ non-empty sub-multisets ~S_1,S_2,\ldots, S_k~, find the partition with the maximum sum ~\displaystyle \sum_{i=1}^k \operatorname{cost}(S_i)~. Here, for ~X=\{x_1, x_2, \ldots, x_q\}~, define ~\operatorname{cost}(X)=x_1\,\&\,x_2\,\&\,\ldots\,\&\,x_q~ where ~\&~ is the bitwise AND operation.

Input

The first line contains two integers ~n~ and ~q~ (~1\le n, q\le 10^5~) — the number of elements in ~S~ and the number of queries.

The second line contains ~n~ non-negative integers ~s_1,s_2,\ldots,s_n~ (~0\le s_i<2^{30}~) — the elements of ~S~.

Each of the next ~q~ lines contains two integers describing the queries. The first integer ~t~ takes a value from ~\{1,2,3\}~.

• If ~t=1~, the next integer is ~x~ (~0\le x<2^{30}~) — the integer to be added to ~S~.

• If ~t=2~, the next integer is ~x~ (~0\le x<2^{30}~; ~x \in S~) — the integer to be removed from ~S~.

• If ~t=3~, the next integer is ~k~ (~1\le k\le |S|~) — the number of sub-multisets to partition into.

Output

For each type ~3~ query, output an integer which is the result of the query on a new line.

Scoring

Sample Input 1

3 5
3 4 5
3 2
1 4
3 3
2 5
3 2

Sample Output 1

7
12
7

Sample Input 2

6 6
5 5 6 6 7 7
3 1
3 2
3 3
3 4
3 5
3 6

Sample Output 2

4
11
18
25
31
36

Notes

For the first example, the initial multiset is ~\{3, 4, 5\}~:

1. One optimal partition for ~k=2~ is ~\{3\}, \{4, 5\}~.

2. The new multiset after adding ~4~ is ~\{3, 4, 4, 5\}~.

3. One optimal partition for ~k=3~ is ~\{3\}, \{4, 4\}, \{5\}~.

4. The new multiset after removing ~5~ is ~\{3, 4, 4\}~.

5. One optimal partition for ~k=2~ is ~\{3\}, \{4, 4\}~.