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.