J. Wedding
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Today Phillip and Aurora have a wedding and all the fairies of the Moors are invited. Aurora got bored a little bit and decided to watch the fairies talk.

At the start $$$n$$$ fairies were present at the wedding, Aurora numbered them from $$$1$$$ to $$$n$$$. Fairy $$$i$$$ is characterized by her talkativeness — a positive integer $$$a_i$$$.

On her watch, Aurora saw $$$q$$$ interesting moments. At the $$$j$$$-th moment one of 3 possible events took place:

  1. Fairy with talkativeness $$$v_j$$$ comes to the wedding. Aurora assigns her the first number which was not used before. For example, the first coming fairy gets the number $$$n + 1$$$, the next  — $$$n + 2$$$ and so on.
  2. Fairy $$$p_j$$$ leaves the wedding.
  3. A dance starts, which is characterized by its expressiveness $$$e_j$$$ — a non-negative number. After the dance, the talkativenesses of all fairies change. If before the dance the fairy had the talkativeness $$$b$$$, then after the dance her talkativeness becomes $$$b \oplus e_j$$$, in other words it becomes xor of $$$b$$$ and $$$e_j$$$.

Aurora wonders how intensively the fairies talk. For that purpose she intends to count the total sum of all talkativenesses of each fairy present at the wedding after each event. Please, help Aurora with this difficult task.

Input

The first line contains two integers - $$$n$$$ and $$$q$$$  — the number of fairies present at the wedding at the start and the number of interesting moments on Aurora's watch ($$$1 \le n, q \le 100\,000$$$).

The second line contains $$$n$$$ integers $$$a_i$$$ — talkativenesses of the fairies who are present at he start ($$$1 \le a_i \le 10^9$$$).

The next $$$q$$$ lines describe interesting moments. Each of them start with an integer $$$t_j$$$ — the type of event ($$$t_j \in \{1, 2, 3\}$$$).

  • If $$$t_j = 1$$$, than there is an integer $$$v_j$$$ — the talkativeness of the newcomer ($$$1 \le v_j \le 10^9$$$). The newcomer gets the first unused number.
  • If $$$t_j = 2$$$, than there follows integer $$$p_j$$$, signaling that fairy $$$p_j$$$ leaves the wedding. It is guaranteed that at that moment fairy $$$p_j$$$ was present at the wedding.
  • If $$$t_j = 3$$$, than there is an integer $$$e_j$$$ — expressiveness of the dance ($$$1 \le e_j \le 10^9$$$).
Output

After each event output the total sum of all talkativenesses of the fairies present at the wedding.

Example
Input
6 5
2 3 9 5 6 6
1 3
3 5
2 2
3 2
2 7
Output
34
37
31
27
23