CF1452F.Divide Powers

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 \gt 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.

你被给定一个由 2 的幂组成的多重集。更准确地说，对于每个从 $0$ 到 $n$（不包括 $n$）的 $i$，你有 $cnt_i$ 个等于 $2^i$ 的元素。

在一次操作中，你可以任选一个满足 $2^l \gt 1$ 的元素，并将其拆分为两个值为 $2^{l - 1}$ 的元素。

你需要执行 $q$ 个查询。每个查询为以下两种类型之一：

• “$1$ $pos$ $val$” —— 将 $cnt_{pos}$ 赋值为 $val$；
• “$2$ $x$ $k$” —— 计算使得值不超过 $2^x$ 的元素个数至少达到 $k$ 所需的最少操作次数。

注意：所有第二类查询均不改变该多重集；即，你仅计算最少操作次数，而并不实际执行这些操作。

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 \lt n$; $0 \le val \le 10^6$);
• "$2$ $x$ $k$" ($0 \le x \lt n$; $1 \le k \le 10^{15}$).

It's guaranteed that there is at least one query of the second type.

第一行包含两个整数 $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 \lt n$；$0 \le val \le 10^6$）；
• “$2$ $x$ $k$”（$0 \le x \lt n$；$1 \le k \le 10^{15}$）。

保证至少存在一个第二类查询。

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.

对于每个第二类查询，输出使至少 $k$ 个元素的值小于等于 $2^x$ 所需的最少操作次数；若无法实现，则输出 $-1$。