Алексей решил попытать счастья в телешоу. Однажды он сходил на викторину. После того, как он идеально ответил на вопросы «Как обычно называют псевдоним в интернете?» («Ум... может быть ник?»), «В честь какого известного изобретателя назвали единицу силы магнитного поля?» («Ум... Никола Тесла?»), он решил посетить гораздо более сложное телешоу: «Что в этом мультимножестве?!».

Это телешоу устроено следующим образом: есть $$$n$$$ мультимножеств, пронумерованных от $$$1$$$ до $$$n$$$. Каждое из них изначально пусто. Затем, происходят $$$q$$$ запросов, где каждый запрос имеет один из четырёх следующих типов:

• 1 x v — присвоить $$$x$$$-му мультимножеству мультимножество из одного элемента $$$\{v\}$$$.
• 2 x y z — присвоить $$$x$$$-му мультимножеству объединение мультимножеств $$$y$$$ и $$$z$$$. For example: $$$\{1, 3\}\cup\{1, 4, 4\}=\{1, 1, 3, 4, 4\}$$$.
• 3 x y z — присвоить $$$x$$$-му мультимножеству произведение $$$y$$$-го и $$$z$$$-го мультимножества. Произведение $$$A \times B$$$ мультимножеств $$$A$$$ и $$$B$$$ определяется как $$$\{ \gcd(a, b)\, \mid\, a \in A,\, b \in B \}$$$, где $$$\gcd(p, q)$$$ обозначает наибольший общий делитель $$$p$$$ и $$$q$$$. Например, $$$\{2, 2, 3\} \times \{1, 4, 6\}=\{1, 2, 2, 1, 2, 2, 1, 1, 3\}$$$.
• 4 x v — вас спрашивают, сколько раз число $$$v$$$ встречается в мультимножестве $$$x$$$. Так как викторина показал себя достаточно сложной в прошлом, то теперь нужно лишь сказать ответ на этот вопрос по модулю $$$2$$$.

Обратите внимание, что $$$x$$$, $$$y$$$, и $$$z$$$ в описании выше не обязательно различны. Для запросов $$$2$$$-го и $$$3$$$-го типа нужно сначала вычислить соответствующую сумму или произведение и лишь затем выполнить присвоение.

Алексея смущают запутанные правила шоу. Помогите ему узнать ответы на все запросы $$$4$$$-го типа.