题目描述

给你一个包含 $n$ 个整数的数组 $a$，初始值 $a_i$ 满足 $0 \leq a_i \leq 1$。你需要处理以下两种请求：

• 1 x：将 $a_x$ 的值变成 $1-a_x$
• 2 k：输出数组中第 $k$ 大的数

其中，第 $k$ 大的数指将数组降序排序后的第 $k$ 个数，比如 $[0,1,0,1]$ 中第 $2$ 大的数为 $1$，是将其降序排序为 $[1,1,0,0]$ 后的其中第 $2$ 个数。

输入格式

第一行包含两个整数 $n,q$ ($1 \leq n,q \leq 10^5$) —— $a$ 数组长度与请求的数量。

第二行包含 $n$ 个整数 $a_1,a_2,a_3,...,a_n$ ($0 \leq a_i \leq 1$) —— $a$ 数组的初始值。

接下来 $q$ 行，每行两个整数。第一个整数为 $t$ ($1 \leq t \leq 2$) —— 请求种类。

• 若 $t=1$，那么第二个整数为 $x$ ($1 \leq x \leq n$) —— 修改 $a_x$ 的值为 $1-a_x$。
• 若 $t=2$，那么第二个整数为 $k$ ($1 \leq k \leq n$) —— 输出第 $k$ 大的值。

保证至少有一个 $t=2$ 的请求。

输出格式

对每个 $t=2$ 的请求，输出一个整数。

样例

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

1
0
1
0