Wedding

Philip and Aurora are getting married today, and all the fairies of the Murky Marshes are invited. Aurora got a little bored and decided to watch how the fairies interact.

At the start, $n$ fairies are at the wedding, and Aurora numbered them from $1$ to $n$. Fairy number $i$ has a sociability $a_i$, a non-negative integer.

During the observation, Aurora saw $q$ interesting moments. At the $j$-th moment, one of three events happened:

1. A fairy with sociability $v_j$ arrives. Aurora gives her the first number that has never been used before. The first arriving fairy gets number $n + 1$, the next one gets $n + 2$, and so on.
2. The fairy with number $p_j$ leaves the wedding.
3. A dance with expressiveness $e_j$, a non-negative integer, is announced. After the dance, every fairy's sociability changes. If a fairy had sociability $b$ before the dance, it becomes $b \oplus e_j$, the bitwise XOR of $b$ and $e_j$.

Aurora wants to know how intensely the fairies interact. After each event, she wants the total sociability of all fairies currently at the wedding. Help Aurora with this task.

The first line contains two integers $n$ and $q$, the number of fairies initially at the wedding and the number of moments ($1 \le n, q \le 100\,000$).

The second line contains $n$ integers $a_i$, the sociability values of the initial fairies ($1 \le a_i \le 10^9$).

Each of the next $q$ lines starts with an integer $t_j$, the event type ($t_j \in \{1, 2, 3\}$).

• If $t_j = 1$, the line contains one more integer $v_j$, the sociability of the arriving fairy ($1 \le v_j \le 10^9$). The arriving fairy gets the first number never used before.
• If $t_j = 2$, the line contains one more integer $p_j$, meaning the fairy with number $p_j$ leaves the wedding. It is guaranteed that this fairy is present at that moment.
• If $t_j = 3$, the line contains one more integer $e_j$, the expressiveness of the dance ($1 \le e_j \le 10^9$).

After each event, print the total sociability of all fairies currently at the wedding.