给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。该数组是非递增的。
让我们考虑一条有 $$$n$$$ 商店的线路。商店从左到右用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。第 $$$i$$$ 店的一顿饭费用等于 $$$a_i$$$。
您应该处理两种类型的 $$$q$$$ 查询:
- 1 x y:对于每个商店 $$$1 \leq i \leq x$$$ 设置 $$$a_{i} = max(a_{i}, y)$$$。
- 2 x y:让我们考虑一个拥有 $$$y$$$ 钱的饥饿者。他访问从第 $$$x$$$ 到第 $$$n$$$ 的商店,如果他可以在当前商店购买一顿饭,他就会购买其中的一件商品。找出他将购买多少顿饭。如果该男子至少有 $$$a_i$$$ 钱,他就可以在商店 $$$i$$$ 买一顿饭,之后他的钱就会减少 $$$a_i$$$。
输入
第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2}, \ldots, a_{n}$$$ $$$(1 \leq a_{i} \leq 10^9)$$$ — 餐费。可以保证 $$$a_1 \geq a_2 \geq \ldots \geq a_n$$$。
接下来的 $$$q$$$ 行包含三个整数 $$$t$$$、$$$x$$$、$$$y$$$ ($$$1 \leq t \leq 2$$$、$$$1\leq x \leq n$$$、$$$1 \leq y \leq 10^9$$$),每个整数描述下一个查询。
保证至少存在一个 $$$2$$$ 类型的查询。
输出
对于 $$$2$$$ 类型的每个查询,在新行上输出答案。
示例
输入 #1
10 6 10 10 10 6 6 5 5 5 3 1 2 3 50 2 4 10 1 3 10 2 2 36 1 4 7 2 2 17
输出 #1
8 3 6 2
注意
在第一个查询中,饥饿的人会在所有商店购买从 $$$3$$$ 到 $$$10$$$ 的餐食。
在第二个查询中,饥饿的人会在 $$$4$$$、$$$9$$$ 和 $$$10$$$ 商店购买食物。
第三次查询后,成本数组 $$$a_1, a_2, \ldots, a_n$$$ 不会改变,将为 $$$\{10, 10, 10, 6, 6, 5, 5, 5, 3, 1\}$$$。
在第四个查询中,饥饿的人会在商店 $$$2$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$9$$$ 和 $$$10$$$ 购买食物。
第五次查询后,成本数组 $$$a$$$ 将为 $$$\{10, 10, 10, 7, 6, 5, 5, 5, 3, 1\}$$$。
在第六个查询中,饥饿的人会在 $$$2$$$ 和 $$$4$$$ 商店购买食物。