A. K-е наибольшее
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Изначально все элементы $$$a$$$ равны $$$0$$$ либо $$$1$$$. Вы должны обработать $$$q$$$ запросов двух типов:

  • 1 x : Присвоить $$$a_x$$$ значение $$$1 - 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$$$) — позиция измененного числа. Вы должны присвоить $$$a_x$$$ значение $$$1 - a_x$$$.
  • Если $$$t = 2$$$, то второе число это $$$k$$$ ($$$1 \le k \le n$$$) — вы должны вывести $$$k$$$-й наибольший элемент массива.

Гарантируется, что будет по крайней мере один запрос второго типа (удовлетворяющий $$$t = 2$$$).

Выходные данные

Для каждого запроса второго типа выведите единственное целое число — ответ на запрос.

Пример
Входные данные
5 5
1 1 0 1 0
2 3
1 2
2 3
2 1
2 5
Выходные данные
1
0
1
0
Примечание

Изначально $$$a = [1, 1, 0, 1, 0]$$$.

В первой операции нужно вывести третье наибольшее значение, которое равно $$$1$$$.

Вторая операция присваивает $$$a_2$$$ значение $$$0$$$, $$$a$$$ становится $$$[1, 0, 0, 1, 0]$$$.

В третьей операции нужно вывести третье наибольшее значение, которое равно $$$0$$$.

В четвертой операции нужно вывести первое наибольшее значение, которое равно $$$1$$$.

В пятой операции нужно вывести пятое наибольшее значение, которое равно $$$0$$$.