Divide Powers

题意翻译

珂朵莉给了你一个只含有 $2$ 的整数次幂的可重集合（换句话说，对于 $\forall 0 \le i \le n$，这个集合中有 $cnt_i$ 个元素等于 $2^i$）。 可以对这个集合做这样的操作： - 将一个数 $2^l$ 切分为两个数 $2^{l-1}$ 现在珂朵莉会问你 $k$ 个问题，每个问题是这样的格式 - $\texttt{1~pos~val}$，表示珂朵莉把 $cnt_{pos}$ 修改为了 $val$； - $\texttt{2~x~k}$，表示珂朵莉问你**如果**她想用上面提到的操作使集合中有至少 $k$ 个元素 **不大于** $2^x$，最少需要操作多少次。**注意：珂朵莉 _并不会_ 真正地修改这个集合，她只需要你计算出最少需要多少次才能达到她的目标**。

题目描述

You are given a multiset of powers of two. More precisely, for each $ i $ from $ 0 $ to $ n $ exclusive you have $ cnt_i $ elements equal to $ 2^i $ . In one operation, you can choose any one element $ 2^l > 1 $ and divide it into two elements $ 2^{l - 1} $ . You should perform $ q $ queries. Each query has one of two types: - " $ 1 $ $ pos $ $ val $ " — assign $ cnt_{pos} := val $ ; - " $ 2 $ $ x $ $ k $ " — calculate the minimum number of operations you need to make at least $ k $ elements with value lower or equal to $ 2^x $ . Note that all queries of the second type don't change the multiset; that is, you just calculate the minimum number of operations, you don't perform them.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n \le 30 $ ; $ 1 \le q \le 2 \cdot 10^5 $ ) — the size of array $ cnt $ and the number of queries. The second line contains $ n $ integers $ cnt_0, cnt_1, \dots, cnt_{n - 1} $ ( $ 0 \le cnt_i \le 10^6 $ ). Next $ q $ lines contain queries: one per line. Each query has one of two types: - " $ 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} $ ). It's guaranteed that there is at least one query of the second type.

输出格式

For each query of the second type, print the minimum number of operations you need to make at least $ k $ elements with a value lower or equal to $ 2^x $ or $ -1 $ if there is no way to do it.

输入输出样例

输入样例 #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

输出样例 #1

4
16
4
-1
0
1

题意翻译

珂朵莉给了你一个只含有 $2$ 的整数次幂的可重集合（换句话说，对于 $\forall 0 \le i \le n$，这个集合中有 $cnt_i$ 个元素等于 $2^i$）。 可以对这个集合做这样的操作： - 将一个数 $2^l$ 切分为两个数 $2^{l-1}$ 现在珂朵莉会问你 $k$ 个问题，每个问题是这样的格式 - $\texttt{1~pos~val}$，表示珂朵莉把 $cnt_{pos}$ 修改为了 $val$； - $\texttt{2~x~k}$，表示珂朵莉问你**如果**她想用上面提到的操作使集合中有至少 $k$ 个元素 **不大于** $2^x$，最少需要操作多少次。**注意：珂朵莉 _并不会_ 真正地修改这个集合，她只需要你计算出最少需要多少次才能达到她的目标**。