Задача . F. Алексей и телешоу

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

Это телешоу устроено следующим образом: есть \(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\)-го типа.