결혼식

오늘 필립과 오로라의 결혼식이 열리고, 늪지대의 모든 요정이 초대되었습니다. 오로라는 조금 지루해져서 요정들이 어떻게 교류하는지 지켜보기로 했습니다.

처음에 결혼식장에는 $n$명의 요정이 있으며, 오로라는 이들에게 $1$부터 $n$까지 번호를 매겼습니다. $i$번 요정은 음이 아닌 정수인 사교성 $a_i$를 가집니다.

관찰하는 동안 오로라는 $q$개의 흥미로운 순간을 보았습니다. $j$번째 순간에는 다음 세 가지 중 하나의 사건이 일어났습니다.

1. 사교성이 $v_j$인 요정이 도착합니다. 오로라는 그 요정에게 지금까지 한 번도 쓰이지 않은 번호 중 가장 작은 번호를 줍니다. 처음 도착한 요정은 $n + 1$번, 다음 요정은 $n + 2$번을 받습니다.
2. $p_j$번 요정이 결혼식장을 떠납니다.
3. 음이 아닌 정수인 표현력 $e_j$의 춤이 선포됩니다. 춤이 끝나면 모든 요정의 사교성이 바뀝니다. 춤 전에 사교성이 $b$였던 요정은 $b \oplus e_j$가 되며, 여기서 $\oplus$는 두 수의 비트별 XOR입니다.

오로라는 요정들이 얼마나 활발하게 교류하는지 알고 싶어 합니다. 각 사건 후에 결혼식장에 있는 모든 요정의 사교성 합을 구해 주세요.

첫 줄에 처음 결혼식장에 있는 요정의 수 $n$과 순간의 수 $q$가 주어집니다 ($1 \le n, q \le 100\,000$).

둘째 줄에 처음 있던 요정들의 사교성 $a_i$가 $n$개 주어집니다 ($1 \le a_i \le 10^9$).

이후 $q$개의 줄에는 각각 사건 유형 $t_j$ ($t_j \in \{1, 2, 3\}$)가 주어집니다.

• $t_j = 1$이면, 도착하는 요정의 사교성 $v_j$가 이어서 주어집니다 ($1 \le v_j \le 10^9$). 도착한 요정은 지금까지 쓰이지 않은 번호 중 가장 작은 번호를 받습니다.
• $t_j = 2$이면, 떠나는 요정의 번호 $p_j$가 이어서 주어집니다. 그 시점에 해당 요정이 결혼식장에 있음이 보장됩니다.
• $t_j = 3$이면, 춤의 표현력 $e_j$가 이어서 주어집니다 ($1 \le e_j \le 10^9$).

각 사건 후에 결혼식장에 있는 모든 요정의 사교성 합을 출력합니다.