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.