题目描述

小度能有一个集合 $S$，包含 $[0, 2^k)$ 之内的元素。接下来，$q$ 个事件将会发生，每个属于以下两种之一：

1. 给出一个整数 $x \in [0, 2^k)$，把 $x$ 插入到 $S$ 中。保证 $x$ 在此次操作之前不在 $S$ 中。
2. 给出一个整数 $x \in [0, 2^k)$。对所有 $y \in S$，计算 $\text{popcount}(x \oplus y)$ 的最小值，其中 $\text{popcount}(a)$ 表示 $a$ 在二进制表示下 1 的个数。保证此次操作之前 $S$ 非空。

请通过告诉他所有类型 2 事件的正确答案，帮助小度能解决这个问题。

输入格式

第一行，两个整数 $q$ 和 $k$（$1 \leq q \leq 5 \cdot 10^6$，$1 \leq k \leq 20$），表示事件个数和值域的大小。

接下来 $q$ 行，每行包含两个整数 $o$ 和 $x$（$o \in 1, 2$，$0 \leq x < 2^k$），描述一次事件，其中 $o$ 是事件的类型，$x$ 是事件的参数。

输出格式

对于每种类型 2 事件，输出一行一个整数表示答案。

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

2
1

解释 #1

对于第一个样例，第一个查询发生时有 $x = 5$ 且 $S = \{2, 3\}$，其中

$$\text{popcount}(5 \oplus 2) = 3, \quad \text{popcount}(5 \oplus 3) = 2,$$

因此查询的答案为 $2$。

第二个查询发生在 $x = 6$ 且 $S = \{2, 3, 4\}$ 时，其中

$$\text{popcount}(6 \oplus 2) = 1, \quad \text{popcount}(6 \oplus 3) = 2, \quad \text{popcount}(6 \oplus 4) = 1,$$

因此查询的答案为 $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