Alex and a TV Show
Contest: Hello 2019
Difficulty rating: 2500
Tags: bitmasks, combinatorics, number theory

Alex decided to try his luck in TV shows. He once went to the quiz named "What's That Word?!". After perfectly answering the questions "How is a pseudonym commonly referred to in the Internet?" ("Um... a nick?"), "After which famous inventor we name the unit of the magnetic field strength?" ("Um... Nikola Tesla?") and "Which rock band performs "How You Remind Me"?" ("Um... Nickelback?"), he decided to apply to a little bit more difficult TV show: "What's in This Multiset?!".

The rules of this TV show are as follows: there are $$$n$$$ multisets numbered from $$$1$$$ to $$$n$$$. Each of them is initially empty. Then, $$$q$$$ events happen; each of them is in one of the four possible types:

- 1 x v — set the $$$x$$$-th multiset to a singleton $$$\{v\}$$$.
- 2 x y z — set the $$$x$$$-th multiset to a union of the $$$y$$$-th and the $$$z$$$-th multiset. For example: $$$\{1, 3\}\cup\{1, 4, 4\}=\{1, 1, 3, 4, 4\}$$$.
- 3 x y z — set the $$$x$$$-th multiset to a product of the $$$y$$$-th and the $$$z$$$-th multiset. The product $$$A \times B$$$ of two multisets $$$A$$$, $$$B$$$ is defined as $$$\{ \gcd(a, b)\, \mid\, a \in A,\, b \in B \}$$$, where $$$\gcd(p, q)$$$ is the greatest common divisor of $$$p$$$ and $$$q$$$. For example: $$$\{2, 2, 3\} \times \{1, 4, 6\}=\{1, 2, 2, 1, 2, 2, 1, 1, 3\}$$$.
- 4 x v — the participant is asked how many times number $$$v$$$ occurs in the $$$x$$$-th multiset. As the quiz turned out to be too hard in the past, participants should now give the answers modulo $$$2$$$ only.

Note, that $$$x$$$, $$$y$$$ and $$$z$$$ described above are not necessarily different. In events of types $$$2$$$ and $$$3$$$, the sum or the product is computed first, and then the assignment is performed.

Alex is confused by the complicated rules of the show. Can you help him answer the requests of the $$$4$$$-th type?

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^6$$$) — the number of multisets and the number of events.

Each of the following $$$q$$$ lines describes next event in the format given in statement. It's guaranteed that $$$1 \leq x,y,z \leq n$$$ and $$$1 \leq v \leq 7000$$$ always holds.

It's guaranteed that there will be at least one event of the $$$4$$$-th type.

Output format:
Print a string which consists of digits $$$0$$$ and $$$1$$$ only, and has length equal to the number of events of the $$$4$$$-th type. The $$$i$$$-th digit of the string should be equal to the answer for the $$$i$$$-th query of the $$$4$$$-th type.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Here is how the multisets look in the example test after each of the events; $$$i$$$ is the number of queries processed so far:

Example input:
4 13
1 1 1
1 2 4
1 3 6
4 4 4
1 4 4
2 2 1 2
2 3 3 4
4 4 4
3 2 2 3
4 2 1
4 2 2
4 2 3
4 2 4

Example output:
010101

Editorial:
Firstly, let's store in a bitset of size $$$7000$$$ an information which elements occur an odd number of times in some multiset. Let's think about the query of the third type like about a convolution. We'll solve it similarly to FFT: we'll change both polynomials (arrays) into a form of "values in points", multiply them by simply multiplying corresponding numbers and then reverse the changing process.
It turns out that the equivalent of "the values in points" method should be as follows: instead of storing the parity of numbers equal to $$$x$$$, store the parity of numbers divisible by $$$x$$$. Why? If we denote by $$$a$$$ the number of elements divisible by some $$$x$$$ in the first multiset and by $$$b$$$ the number of elements divisible by $$$x$$$ in the second multiset, then the number of elements divisible by $$$x$$$ in their product is $$$a \cdot b$$$. Thanks to that, we can multiply easily now. The multiplication is now just a bitwise AND operation. We can also add the multisets in this form as it's a bitwise XOR operation.
But of course, we cannot change the form each time when we want to multiply two multisets. It can be done in $$$O(d \cdot \log{d})$$$ for $$$d=7000$$$, but it's too slow. Instead, we commit to keeping each multiset in the changed form all the time.
How to answer for parity of the number of occurrences of some number $$$x$$$ in a multiset without changing it to normal form? Inclusion-exclusion principle tells us that we should take the numbers from positions $$$i$$$ which are divisible by $$$x$$$ and for which $$$\frac{i}{x}$$$ is square-free. Each of these numbers should be multiplied by $$$1$$$ or $$$-1$$$. Luckily, we are calculating the results modulo $$$2$$$ and because $$$1 \equiv -1~(mod~2)$$$, we just add everything up without multiplying by $$$\pm 1$$$. We can prepare the bitsets for every possible query of type $$$1$$$ and $$$4$$$. This allows us to answer every query in $$$O(d/32)$$$.