【MX-X6-T6】機械生命体

原题链接：<https://oier.team/problems/X6G>。 --- > _許してよ、もう$\\$ 分かってよ$\\$ 此処の正体を$\\$ 僕ですら僕を$\\$ 愛せないんだって$\\$ 感情を持った代償をくれよ$\\$ 狂っている_ > > _—— [機械生命体 - Nanatsukaze](https://music.163.com/#/song?id=2627128854)_ 二进制的运算和记忆，能够在机械生命体中还原出人类的情感吗？

维护一个**可重集** $S$，初始为空。支持如下操作： - `1 x`，你需要在 $S$ 中加入一个数 $x$。 - `2 x`，你需要在 $S$ 中删除一个数 $x$。保证此时 $S$ 中存在至少一个 $x$。如果存在多个 $x$，则仅删除一个。 - `3 x k v`，你需要对 $S$ 中所有满足 $\operatorname{lowbit}(x\oplus y)\geq 2^k$ 的 $y$ 增加 $v$ 并对 $2^{32}$ 取模。 - `4 x`，你需要求出 $\max\limits_{y\in S} \operatorname{lowbit}(x\oplus y)$。保证此时 $S$ 不为空。 其中 $\operatorname{lowbit}(x)$ 表示最大的整数 $k$，使得 $k$ 是 $2$ 的整数次幂并且整除 $x$。$\oplus$ 代表[按位异或](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677)。 **特殊的，我们在本题定义 $\boldsymbol{\textbf{lowbit}(0)=2^{32}}$。**

第一行一个整数 $q$，代表询问数量。 接下来 $q$ 行，每行首先输入一个整数 $opt$ 表示操作类型；如果 $opt=3$，则接下来依次输入三个整数 $x,k,v$，否则接下来输入一个整数 $x$。

对每一次 `4` 操作，输出一个整数代表答案。

11
1 1
1 2
1 2
1 3
1 4
4 10
3 2 1 2
2 4
4 16
2 4
4 16

8
4
2

**【样例解释】** 第 $6$ 次操作时，集合为 $\{1,2,2,3,4\}$，查询 $10$ 时，$\operatorname{lowbit}(10\oplus 2)=\operatorname{lowbit}(8)=8$ 为最大值。 第 $7$ 次操作后，所有 $\operatorname{lowbit}(x\oplus 2)\geq 2^1$ 的数增加 $2$，集合中满足条件的数有 $2,2,4$，于是集合变为 $\{1,3,4,4,6\}$。 第 $8$ 次操作删去一个 $4$，集合变为 $\{1,3,4,6\}$。 第 $9$ 次操作查询 $16$，$\operatorname{lowbit}(16\oplus 4)=\operatorname{lowbit}(20)=4$ 为最大值。 第 $10$ 次操作再次删去一个 $4$，集合变为 $\{1,3,6\}$。 第 $11$ 次操作查询 $16$，$\operatorname{lowbit}(16\oplus 6)=\operatorname{lowbit}(22)=2$ 为最大值。 **【数据范围】** 对于所有数据，$1\leq q\leq 5\times 10^5$，$0\leq x,y,v\leq 2^{32}-1$，$0\leq k\leq 32$。 **捆绑测试**，共 5 个 Subtask，具体限制如下所示： - Subtask 1（7 pts）：$q\leq 10^3$。 - Subtask 2（16 pts）：不存在 3 操作。 - Subtask 3（21 pts）：对于 3 操作，$k=0$。 - Subtask 4（28 pts）：对于 3 操作，$v=1$。 - Subtask 5（28 pts）：无特殊限制。