×

# 计蒜客

1. 题库
2. Set
3. 问答
• 15.17%
• 1500ms
• 524288K

Shinku is very interested in the set. One day, she got $n$ sets, and the $i$-th number $a_i$ is in the $i$-th set. But she doesn't think it is interesting enough, so she applies $m$ magic to these sets. There are three kinds of magic:

$1\ u\ v$: If the $u$-th and $v$-th numbers are not in one set, then the Shinku's magic will merge the set containing the $u$-th number and the set containing the $v$-th number.

$2\ u$: Shinku's magic adds $1$ to each number in the set containing the $u$-th number.

$3\ u\ k\ x$: Shinku can immediately know how many numbers $t$ in the set containing the $u$-th number satisfy $t\equiv x (\bmod\ 2^k)(0 \le k\le 30,0\le x<2^k)$.

But unfortunately, for some reason the type $3$ magic fails. So Shinku wants you to tell her the answer after every type $3$ magic.

Note that there can be multiple numbers with the same value in one set, that is, numbers with the same value will not disappear when merged.

### Input

The first line contains two integers $n, m(1 \le n, m \le 6 \times 10^5)$, the number of initial sets and the number of the magic.

The second line contains $n$ integers. The $i$-th number $a_i(0 \le a_i \le 10^9)$ is the number in the $i$-th set initially.

The next $m$ lines describe the sequence of magic. The $i$-th line describes the $i$-th magic. Each magic is a magic as described above.

### Output

For each type $3$ magic, output the answer you are asked to calculate.

### Hint

After the first operation, the numbers are $2,3,4$, sets are $\lbrace 2,4 \rbrace \lbrace 3 \rbrace$

For the second operation, the third number is in $\lbrace 2,4 \rbrace, 2 \equiv 0\pmod {2^1}, 4 \equiv 0\pmod {2^1}$, so the answer is $2$.

After the third operation, the numbers are $2,4,4$, sets are $\lbrace 2,4 \rbrace \lbrace 4 \rbrace$

After the forth operation, the numbers are $2,4,4$, sets are $\lbrace 2,4,4 \rbrace$

For the fifth operation, ,the third number is in $\lbrace 2,4,4 \rbrace, 2 \equiv 0\pmod {2^1}, 4 \equiv 0\pmod {2^1}$,
$4 \equiv 0\pmod {2^1}$, so the answer is $3$.

#### 样例输入

3 5
2 3 4
1 1 3
3 3 1 0
2 2
1 2 3
3 3 1 0

#### 样例输出

2
3

• main.c