K. Ragdoll
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

Once there was a lovely ragdoll cat, named Little Zara, who liked trees and math. One day she met the doge Adam. Adam had just planted some trees each consisting of only one node. The nodes were numbered from $$$1$$$ to $$$n$$$, and the $$$i$$$-th node was assigned a value $$$a_i$$$. Adam liked pairing tree nodes, but he disliked some node pairs. A pair of nodes $$$(i, j)$$$ was considered bad if $$$i$$$ and $$$j$$$ were in the same tree and $$$\operatorname{gcd}(a_i,a_j)=a_i\oplus a_j$$$, where $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$, and $$$\oplus$$$ denotes the bitwise XOR operation. Adam wondered how many bad pairs there were in his forest.

Zara was good at solving problems about trees and math, so she could answer Adam's question in a short time. However, Adam was so naughty a dog that he would repeatedly change the forest slightly and ask Zara his question again after the change.

The changes Adam might make are listed here:

  1. Adam plants a new tree with only one node numbered $$$x$$$ and assigned a value $$$v$$$.
  2. Adam uses magic to merge the tree containing the node $$$x$$$ and the one containing the node $$$y$$$. If $$$x$$$ and $$$y$$$ are in the same tree before the operation, the magic fails and has no effect.
  3. Adam changes the value of node $$$x$$$ to $$$v$$$.

Now you are expected to help Zara answer all questions Adam asked, in order that they could sing and dance together happily.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 2 \times 10^5$$$), representing the number of nodes in the original forest and the number of changes Adam would make, respectively.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \times 10^5$$$).

Each of the next $$$m$$$ lines describes a change Adam made, starting with an integer $$$t$$$ ($$$1 \leq t \leq 3$$$) representing the type of the change.

  • If $$$t = 1$$$, it will be followed by two integers $$$x$$$ and $$$v$$$ ($$$n \lt x \leq n + m$$$, $$$1 \leq v \leq 2 \times 10^5$$$). It is guaranteed that $$$x$$$'s are distinct in all changes of the first type.
  • If $$$t = 2$$$, it will be followed by two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n + m$$$). It is guaranteed that the node $$$x$$$ and $$$y$$$ already exist in the forest.
  • If $$$t = 3$$$, it will be followed by two integers $$$x$$$ and $$$v$$$. ($$$1 \leq x \leq n + m$$$, $$$1 \leq v \leq 2 \times 10^5$$$). It is guaranteed that the node $$$x$$$ already exists in the forest.
Output

For each change Adam made, print one line with a single integer, representing the number of bad pairs in the forest after the change.

Examples
Input
3 6
3 2 1
2 1 2
1 5 3
2 1 2
2 3 2
2 5 1
3 3 2
Output
1
1
1
1
2
4
Input
10 6
6 6 4 7 7 4 6 4 6 5
2 5 1
2 10 7
2 8 7
2 7 2
2 6 2
2 9 1
Output
1
1
3
4
7
8