All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

May Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?