P11160 [MX-X6-T6] Mechanical Lifeform.

Original link: 。 --- > _Please forgive me, already$\\$ Understand it$\\$ The true form of this place$\\$ Even I cannot$\\$ Love myself$\\$ Give me the price for having feelings$\\$ I am going crazy_ > > _—— [Mechanical Lifeform - Nanatsukaze](https://music.163.com/#/song?id=2627128854)_ Can binary operations and memory bring back human emotions in a mechanical lifeform?

Maintain a **multiset** $S$, initially empty. It supports the following operations: - `1 x`: Insert a number $x$ into $S$. - `2 x`: Delete a number $x$ from $S$. It is guaranteed that at this time $S$ contains at least one $x$. If there are multiple $x$, delete only one. - `3 x k v`: For all $y$ in $S$ that satisfy $\operatorname{lowbit}(x\oplus y)\geq 2^k$, increase $y$ by $v$ and take modulo $2^{32}$. - `4 x`: Query $\max\limits_{y\in S} \operatorname{lowbit}(x\oplus y)$. It is guaranteed that at this time $S$ is not empty. Here, $\operatorname{lowbit}(x)$ denotes the largest integer $k$ such that $k$ is an integer power of $2$ and divides $x$. $\oplus$ denotes [bitwise XOR](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677)。 **In particular, in this problem we define $\boldsymbol{\textbf{lowbit}(0)=2^{32}}$.**

The first line contains an integer $q$, the number of queries. Then follow $q$ lines. Each line first contains an integer $opt$ indicating the operation type. If $opt=3$, then three integers $x,k,v$ follow in order; otherwise, one integer $x$ follows.

For each operation `4`, output one integer representing the answer.

**Sample Explanation.** At the 6th operation, the multiset is $\{1,2,2,3,4\}$. When querying $10$, $\operatorname{lowbit}(10\oplus 2)=\operatorname{lowbit}(8)=8$ is the maximum. After the 7th operation, all numbers with $\operatorname{lowbit}(x\oplus 2)\geq 2^1$ are increased by $2$. The numbers in the multiset that satisfy the condition are $2,2,4$, so the multiset becomes $\{1,3,4,4,6\}$. At the 8th operation, one $4$ is deleted, and the multiset becomes $\{1,3,4,6\}$. At the 9th operation, query $16$. $\operatorname{lowbit}(16\oplus 4)=\operatorname{lowbit}(20)=4$ is the maximum. At the 10th operation, one $4$ is deleted again, and the multiset becomes $\{1,3,6\}$. At the 11th operation, query $16$. $\operatorname{lowbit}(16\oplus 6)=\operatorname{lowbit}(22)=2$ is the maximum. **Constraints.** For all testdata, $1\leq q\leq 5\times 10^5$, $0\leq x,y,v\leq 2^{32}-1$, $0\leq k\leq 32$. **Bundled tests**, a total of 5 subtasks, with the specific limits as follows: - Subtask 1 (7 pts): $q\leq 10^3$. - Subtask 2 (16 pts): There is no operation `3`. - Subtask 3 (21 pts): For operation `3`, $k=0$. - Subtask 4 (28 pts): For operation `3`, $v=1$. - Subtask 5 (28 pts): No special constraints. Translated by ChatGPT 5