Xor and Insert

★★★★★

4.4

30 votes

Advanced Data Structures, Data Structures, Medium, Tries

Details

Submissions

Discussion

Editorial

Problem

At the first, you have a set $S = {0}$ (it contains a zero). There are three types of query:

- $1\ x$ : Add $x$ to the set.
- $2\ x$ : For each element like $y$ set $y = y \oplus x$ ( $\oplus$ means bitwise exclusive OR, More information).
- $3$ : Print the minimum of the set.

Input

The first line contains an integer $q$ ( $q \le 500\ 000$ ).
In the next $q$ lines, queries are given.
$x \le 10^9$ .

Output

For each query of the third type, print the answer.

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

The minimum is 0.
The number $7$ added to $S$ .
The minimum is still zero.
All of the numbers in $S$ are changed to their xor with $4$ .
All of the numbers in $S$ are changed to their xor with $8$ .
All of the numbers in $S$ are changed to their xor with $3$ .
The number $10$ added to $S$ .
The number $3$ added to $S$ .
The minimum is now $3$ .
All of the numbers in $S$ are changed to their xor with $1$ .