Xor and Insert
Tag(s):

## Advanced Data Structures, Data Structures, Medium, Trie

Problem
Editorial
Analytics

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.

SAMPLE INPUT
10
3
1 7
3
2 4
2 8
2 3
1 10
1 3
3
2 1

SAMPLE OUTPUT
0
0
3

Explanation
1. The minimum is 0.
2. The number $7$ added to $S$.
3. The minimum is still zero.
4. All of the numbers in $S$ are changed to their xor with $4$.
5. All of the numbers in $S$ are changed to their xor with $8$.
6. All of the numbers in $S$ are changed to their xor with $3$.
7. The number $10$ added to $S$.
8. The number $3$ added to $S$.
9. The minimum is now $3$.
10. All of the numbers in $S$ are changed to their xor with $1$.
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

May Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Python > Getting Started
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Data Structures > Advanced Data Structures