## XOR Game

View as PDF

Points: 1
Time limit: 3.0s
Memory limit: 256M

Problem types

Sinan and Fahri are playing an XOR game. Initially, Sinan has an empty set of integers. Then a sequence of $$\mathbf{N}$$ events happens. There are two types of events:

• Sinan chooses integer $$\mathbf{A}$$ and adds it to the set;
• Fahri chooses integer $$\mathbf{A}$$ and passes it to Sinan who finds integer $$B$$ in the set such that integer $$\mathbf{A} \oplus \mathbf{B}$$ contains minimal possible number of 1s in its binary representation. Here $$\oplus$$ is a bitwise exclusive or operation, for more details check Wikipedia page.

Your taks is to help Sinan finding minimal possible number of 1 bits in binary representaion of $$\mathbf{A} \oplus \mathbf{B}$$.

#### Input

The first line contains integer $$\mathbf{N}$$. Each of the following $$\mathbf{N}$$ lines describes an event as two integers $$\mathbf{T}$$ and $$\mathbf{A}$$ separated by a single space. Here $$\mathbf{T}$$ is an event type.

#### Output

For each event of the second type print the corresponding minimal number of 1 bits in a separate line.

#### Constraints

• $$2 <= \mathbf{N} <= 2 \cdot 10^5$$,
• $$1 <= \mathbf{T} <= 2$$,
• $$0 <= \mathbf{A} <= 10^6$$,
• in the first event $$\mathbf{T} = 1$$.

#### Example

Input

4
1 2
2 1
1 1
2 3

Output

2
1

Input

5
1 2
1 4
1 8
2 3
2 14
1
2