# 描述

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 mmm magic to these sets. There are three kinds of magic:

1 $1\ u\ v$: If the uuu-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 $2\ u$: Shinku’s magic adds $1$ to each number in the set containing the $u$-th number.

3 $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 nnn 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$.

# 思路

• 容易想到使用01字典树来维护一个size域。
• 这样的话第三个操作就是查询字典树上某个结点size的值。
• 第一个操作就是字典树的合并，类似线段树的合并，需要利用可持久化的思想共用结点来节约内存。
• 第二个操作就是打懒标记。在下推的时候，如果懒标记是个奇数就意味着要交换左右子树。
• 内存卡得比较紧，写了vector内存池就MLE了QAQ。
• 具体实现见代码。（难得写一次指针感觉还是蛮舒服的）
• 实际上pushdown只会递归交换一条链上的点的左右子树，因此不打懒标记也可以。

0%