给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。最初 $$$a$$$ 的所有元素要么是 $$$0$$$ 要么是 $$$1$$$。您需要处理两种类型的 $$$q$$$ 查询:
- 1 x :将值 $$$1 - a_x$$$ 分配给 $$$a_x$$$。
- 2 k :打印数组中第 $$$k$$$ 的最大值。
提醒一下,$$$k$$$ 数组 $$$b$$$ 的第一个最大值定义如下:
- 按非递增顺序对数组进行排序,返回其中第 $$$k$$$ 个元素。
例如,数组$$$[0, 1, 0, 1]$$$中的第二大元素是$$$1$$$,按非升序排序后变成$$$[1, 1, 0, 0]$$$,该数组中的第二个元素等于$$$1$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — 给定数组的长度和查询的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$) — 初始数组的元素。
以下 $$$q$$$ 行中的每一行都包含两个整数。第一个整数是 $$$t$$$ ($$$1 \le t \le 2$$$) — 查询的类型。
- 如果 $$$t = 1$$$,第二个整数是 $$$x$$$ ($$$1 \le x \le n$$$) — 修改后的数字的位置。您必须将值 $$$1 - a_x$$$ 分配给 $$$a_x$$$。
- 如果 $$$t = 2$$$,第二个整数是 $$$k$$$ ($$$1 \le k \le n$$$) — 您需要打印数组中第 $$$k$$$ 的最大值。
保证至少有一个第二类型的查询(满足 $$$t = 2$$$)。
输出
对于第二种类型的每个查询,打印一个整数 - 查询的答案。
示例
输入 #1
5 5 1 1 0 1 0 2 3 1 2 2 3 2 1 2 5
输出 #1
1 0 1 0
注意
最初 $$$a = [1, 1, 0, 1, 0]$$$。
第一个操作是打印第三大值,即$$$1$$$。
第二个操作是将$$$a_2$$$ 赋值为$$$0$$$,$$$a$$$ 变为$$$[1, 0, 0, 1, 0]$$$。
第三个操作是打印第三大的值,它是$$$0$$$。
第四个操作是打印第一个最大值,它是$$$1$$$。
最后一个操作是打印第五大值,它是$$$0$$$。