Problem Description

Rikka has a set $S$ containing elements in $[0, 2^k)$, which is initially empty. Then $q$ events will happen, each of which is one of the following two types:

1. Given an integer $x \in [0, 2^k)$, insert $x$ into $S$. It is guaranteed that $x$ is not in $S$ before this operation.
2. Given an integer $x \in [0, 2^k)$. For all $y \in S$, compute the minimum value of $\operatorname{popcount}(x \oplus y)$. It is guaranteed that $S$ is non-empty before this operation.

Please help Rikka solve this problem by outputting the correct answer for every type $2$ event.

Input Format

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.

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

Output Format

For each type $2$ event, output one line with one integer representing the answer.

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

2
1

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

1
2
1
0
0
1

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

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

Hint

For the first sample, when the first query happens, $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 happens 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$.

Translated by ChatGPT 5