题目背景

許してよ、もう$\\$ 分かってよ$\\$ 此処の正体を$\\$ 僕ですら僕を$\\$ 愛せないんだって$\\$ 感情を持った代償をくれよ$\\$ 狂っている

—— 機械生命体 - Nanatsukaze

二进制的运算和记忆，能够在机械生命体中还原出人类的情感吗？

题目描述

维护一个可重集 $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$ 代表按位异或。

特殊的，我们在本题定义 $\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）：无特殊限制。