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 $op("gcd") (a_i, a_j) = a_i plus.circle a_j$, where $op("gcd") (x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$, and $plus.circle$ 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:
Now you are expected to help Zara answer all questions Adam asked, in order that they could sing and dance together happily.
The first line contains two integers $n$ and $m$ ($1 <= n <= 10^5$, $1 <= m <= 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, \\dots, a_n$ ($1 <= a_i <= 2 times 10^5$).
Each of the next $m$ lines describes a change Adam made, starting with an integer $t$ ($1 <= t <= 3$) representing the type of the change.
For each change Adam made, print one line with a single integer, representing the number of bad pairs in the forest after the change.
## Input
The first line contains two integers $n$ and $m$ ($1 <= n <= 10^5$, $1 <= m <= 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, \\dots, a_n$ ($1 <= a_i <= 2 times 10^5$).Each of the next $m$ lines describes a change Adam made, starting with an integer $t$ ($1 <= t <= 3$) representing the type of the change. If $t = 1$, it will be followed by two integers $x$ and $v$ ($n < x <= n + m$, $1 <= v <= 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 <= x, y <= 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 <= x <= n + m$, $1 <= v <= 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.
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the number of nodes and number of operations, respectively.
Let $ A = (a_1, a_2, \dots, a_n) $ be the array of node values, where $ a_i \in \mathbb{Z}^+ $.
Let $ F $ be a forest (undirected acyclic graph) of $ n $ nodes, initially with each node as a separate component.
Let $ \text{gcd}(x, y) $ denote the greatest common divisor of $ x $ and $ y $.
Let $ x \oplus y $ denote the bitwise XOR of $ x $ and $ y $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $, $ 1 \leq m \leq 2 \times 10^5 $
2. $ 1 \leq a_i \leq 2 \times 10^5 $ for all $ i \in \{1, \dots, n\} $
**Bad Pair Definition**
A pair of nodes $ (i, j) $, $ i < j $, is *bad* if:
- $ i $ and $ j $ are in the same connected component of $ F $, and
- $ \text{gcd}(a_i, a_j) = a_i \oplus a_j $
**Operations**
Each operation is of type $ t \in \{1, 2, 3\} $:
- **Type 1**: Merge the connected components containing nodes $ u $ and $ v $ (if not already connected).
- **Type 2**: Update the value of node $ u $ to $ x $: $ a_u \gets x $.
- **Type 3**: Query the total number of bad pairs in the current forest.
**Objective**
After each of the $ m $ operations, output the total number of bad pairs in the forest, defined as:
$$
\sum_{\substack{(i,j) \in E_F \\ i < j}} \mathbf{1}_{\text{gcd}(a_i, a_j) = a_i \oplus a_j}
$$
where $ E_F $ is the set of unordered pairs of nodes in the same connected component.