Background

Original link: https://oier.team/problems/X6G。

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

Can binary operations and memory bring back human emotions in a mechanical lifeform?

Problem Description

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。

In particular, in this problem we define $\boldsymbol{\textbf{lowbit}(0)=2^{32}}$.

Input Format

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.

Output Format

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

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

Hint

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