Вам задано мультимножество степеней двоек. Точнее, для каждого \(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\).
Заметим, что запросы второго типа не влияют на мультимножество; таким образом, вы только считаете количество операций, но не применяете их.
Выходные данные
Для каждого запроса второго типа, выведите минимальное количество операций, необходимых для того, чтобы получить хотя бы \(k\) элементов со значением не более \(2^x\), либо \(-1\), если невозможно так сделать.
Примеры
| № | Входные данные | Выходные данные |
|
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
|