你被赋予了一组由二组成的多重权力。更准确地说,对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$i$$$ 不包括,您拥有等于 $$$2^i$$$ 的 $$$cnt_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$$$(如果没有办法做到)。
示例
输入 #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