2193: Лепрекон
Перегляд у форматі PDFУ серіалі 'Американські боги' несподівано для нас існують боги і підвладні їм істоти. Божевільний Суїні - лепрекон і, як у кожного поважаючого себе лепрекона, у нього є горщик із золотими монетами, причому деякі з золотих монет є щасливими. У нього є ~n~ монет і для кожної щасливої відомо, що її номінал дорівнює (операція побітового виключного АБО - 'XOR') номіналів всіх монет, крім неї.
Суїні довірив вам свій горщик з монетами, але тепер у нього є ~q~ прохань до вас. Прохання бувають трьох типів:
1. Видалити з горщика монету номіналу ~x~, при цьому гарантується, що монета такої ваги присутня на даний момент.
2. Додати в горщик монету номіналу ~x~.
3. Знайти кількість щасливих монет.
Input
У першому рядку дано два цілих числа ~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~). Типи запитів і номінали монет - цілі числа.
Output
Для кожного запиту третього типу виведіть кількість щасливих монет.
Sample Input 1
1 3
1
3
2 1
3
Sample Output 1
0
2
Notes
~i~-й біт побітового виключного АБО чисел ~a~ і ~b~ дорівнює 1, тоді і тільки тоді, коли ~i~-і біти чисел ~a~ і ~b~ різні.
Розглянемо «XOR» чисел 4 і 5, 4 = ~100_2~, а 5 = ~101_2~, тоді їх побітне виключне АБО дорівнює ~001_2~, тобто 1 в десятковій системі числення.
Розберемо приклад з умови. Спочатку є тільки одна монета, отже «XOR» всіх монет, крім неї, дорівнює 0, а отже щасливих монет немає. Потім додається ще одна монета вагою 1. «XOR» множини з однієї монети дорівнює її вазі, отже обидві монети щасливі.
Коментарі
побітне виключне АБО двход числе дорівнює різниці її ХОR. Чому дорівнює побітне виключення трьох та більше чисел?
Побітове виключення це і є ксор. Для трьох і більше чисел працює розподільна властивість. (x1 ^ x2) ^ x3 = x1 ^ (x2 ^ x 3)