Please use efficient input and output methods.

Rikka has a set $S$ containing elements in the range $[0, 2^k)$. There are $q$ events that will occur, each of which is one of the following two types:

• Given an integer $x \in [0, 2^k)$, insert $x$ into $S$. It is guaranteed that $x$ is not in $S$ before this operation.
• Given an integer $x \in [0, 2^k)$, calculate the minimum value of $\operatorname{popcount}(x \oplus y)$ for all $y \in S$, where $\operatorname{popcount}(a)$ denotes the number of $1$s in the binary representation of $a$. It is guaranteed that $S$ is non-empty before this operation.

Help Rikka solve this problem by providing the correct answer for all type $2$ events.

Input

The first line contains two integers $q$ and $k$ ($1 \leq q \leq 5\cdot 10^6$, $1 \leq k \leq 20$), representing the number of events and the size of the value range.

Each of the next $q$ lines contains two integers $o$ and $x$ ($o \in \{1, 2\}$, $0 \leq x < 2^k$), describing an event, where $o$ is the type of the event and $x$ is the parameter of the event.

Output

For each type $2$ event, output a single integer on a new line representing the answer.

Examples

Input 1

5 3
1 2
1 3
2 5
1 4
2 6

Output 1

2
1

Input 2

12 4
1 5
1 11
2 7
2 12
1 3
2 2
1 6
1 0
2 5
2 11
1 14
2 1

Output 2

1
2
1
0
0
1

Input 3

40 5
1 7
2 0
2 18
2 23
2 13
2 5
2 30
1 1
2 9
2 5
2 29
2 10
2 29
2 18
2 29
1 20
2 19
2 4
1 18
2 13
2 14
2 10
2 1
1 15
2 28
2 2
1 0
2 19
1 8
2 8
1 13
2 7
1 31
2 1
1 14
2 6
1 30
2 9
2 20
2 4

Output 3

3
3
1
2
1
3
1
1
3
3
3
3
3
2
1
2
2
2
0
1
1
1
0
0
0
1
1
0
1

Note

For the first example, when the first query occurs, $x = 5$ and $S = \{2, 3\}$. We have $\operatorname{popcount}(5 \oplus 2) = 3$ and $\operatorname{popcount}(5 \oplus 3) = 2$, so the answer to the query is $2$. The second query occurs when $x = 6$ and $S = \{2, 3, 4\}$. We have $\operatorname{popcount}(6 \oplus 2) = 1$, $\operatorname{popcount}(6 \oplus 3) = 2$, and $\operatorname{popcount}(6 \oplus 4) = 1$, so the answer to the query is $1$.