В сериале «Американские боги», внезапно, существуют боги и подвластные им существа. Сума- сшедший Суини — лепрекон и, как у каждого уважающего себя лепрекона, у него есть горшочек с золотыми монетами, притом некоторые из золотых монет являются счастливыми. У него n монет и для каждой счастливой известно, что ее номинал равен $⊕$ (операция побитового исключающего или — «XOR») номиналов всех монет, кроме нее. Суини доверил вам свой горшок с монетами, но теперь у него есть $q$ просьб к вам. Просьбы бывают трех типов:

1. Удалить из горшочка монету номинала $x$, при этом гарантируется, что монета такого веса присутствует на данный момент.
2. Добавить в горшочек монету номинала $x$.
3. Найти количество счастливых монет.

Входные данные

В первой строке даны два целых числа n и q ($1 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^5$) — изначальное число монет и количество запросов. Во второй строке даны n целых чисел $a_i$ ($1 \le a_i \le 2 \cdot 10^9$), где $a_i$ — номинал $i$-й монеты. В следующих q строках сначала задан тип запроса $t$ ($1 \le t \le 3$) и, если запрос первого или второго типа, затем дан номинал монеты $x$ ($1 \le x \le 2 \cdot 10^9$). Типы запросов и номиналы монет — целые числа.

Выходные данные

Для каждого запроса третьего типа выведите количество счастливых монет.

Подзадачи