×

计蒜客

  1. 题库
  2. Set
  3. 问答
  • 15.08%
  • 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

题目来源

ACM-ICPC 2018 南京赛区网络预赛

想挑战这道题吗

  • main.c