F. Разделяем степени
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано мультимножество степеней двоек. Точнее, для каждого $$$i$$$ от $$$0$$$ до $$$n$$$ невключительно у вас есть $$$cnt_i$$$ элементов равных $$$2^i$$$.

За одну операцию, вы можете выбрать один любой элемент $$$2^l > 1$$$ и разделить его на два элемента $$$2^{l - 1}$$$.

Вам нужно обработать $$$q$$$ запросов. Каждый запрос имеет один из двух типов:

  • «$$$1$$$ $$$pos$$$ $$$val$$$» — присвоить $$$cnt_{pos} := val$$$;
  • «$$$2$$$ $$$x$$$ $$$k$$$» — посчитать минимальное количество операций необходимых для того, чтобы сделать не менее $$$k$$$ элементов со значениями не более $$$2^x$$$.

Заметим, что запросы второго типа не влияют на мультимножество; таким образом, вы только считаете количество операций, но не применяете их.

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

В первой строке заданы два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 30$$$; $$$1 \le q \le 2 \cdot 10^5$$$) — размер массива $$$cnt$$$ и количество операций.

Во второй строке заданы $$$n$$$ целых чисел $$$cnt_0, cnt_1, \dots, cnt_{n - 1}$$$ ($$$0 \le cnt_i \le 10^6$$$).

В следующих $$$q$$$ строках заданы запросы: по одному в строке. Каждый запрос имеет один из двух типов:

  • «$$$1$$$ $$$pos$$$ $$$val$$$» ($$$0 \le pos < n$$$; $$$0 \le val \le 10^6$$$);
  • «$$$2$$$ $$$x$$$ $$$k$$$» ($$$0 \le x < n$$$; $$$1 \le k \le 10^{15}$$$).

Гарантируется, что есть хотя бы один запрос второго типа.

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

Для каждого запроса второго типа, выведите минимальное количество операций, необходимых для того, чтобы получить хотя бы $$$k$$$ элементов со значением не более $$$2^x$$$, либо $$$-1$$$, если невозможно так сделать.

Пример
Входные данные
6 11
0 1 0 0 1 0
2 1 5
2 4 18
1 1 0
2 2 5
2 0 17
1 0 3
2 1 2
1 1 4
1 4 0
1 5 1
2 2 8
Выходные данные
4
16
4
-1
0
1