题目描述

请选用较为快速的输入输出方法。

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

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

请通过告诉她所有类型 $2$ 事件的正确答案，帮助 Rikka 解决这个问题。

输入格式

第一行，两个整数 $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$ 事件，输出一行一个整数表示答案。

样例

样例输入 1

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

样例输出 1

2
1

样例输入 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

样例输出 2

1
2
1
0
0
1

样例输入 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

样例输出 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

样例解释

对于第一个样例，第一个查询发生时有 $x = 5$ 且 $S = \{2, 3\}$，其中 $\operatorname{popcount}(5 \oplus 2) = 3$，$\operatorname{popcount}(5 \oplus 3) = 2$，因此查询的答案为 $2$。第二个查询发生在 $x = 6$ 且 $S = \{2, 3, 4\}$ 时，其中 $\operatorname{popcount}(6 \oplus 2) = 1$，$\operatorname{popcount}(6 \oplus 3) = 2$，$\operatorname{popcount}(6 \oplus 4) = 1$，因此查询的答案为 $1$。