题目描述

桃子是一位包包爱好者，她经常会去核桃大街上买包。

已知核桃大街上有 $n$ 个店铺，它们全部都卖包包，门牌号码从 $1$ 到 $n$，并且每家店的橱窗上都会摆放有一只当季爆款包包，其中第 $i$ 家店的爆款包包的价格为 $a_i$ 元。并且这 $n$ 家店满足 $a_1 \ge a_2 \ge \ldots \ge a_n$（即门牌号较大的店爆款包包的价格不会高于门牌号较小的店的爆款包包价格）。

接下来会发生 $q$ 个事件，事件只有两种类型：

• 1 x y：表示有关部门给前 $x$ 家店铺（即门牌号 $\le x$ 的所有店铺）制定了一个当季爆款参考价格 $y$，对于第 $i$ 家店铺，若其爆款价格低于 $y$ ，则需要更新一家爆款价格为 $y$（即令 $a_i = \max(a_i,y)$）；
• 2 x y：表示桃子带着 $y$ 元钱来到了核桃大街，从第 $x$ 家店铺开始逛起，一直逛到第 $n$ 家店铺（即她逛店铺的顺序为 $x+1, x+2, \ldots, n-1, n$），她会依次去逛每一家店铺，若当前（假设为第 $i$ 个）店铺的爆款包包价格 $a_i$ 没有超过她身上的钱，则她会购买这个包包，于是，她这次购买的包包数量增加了 $1$，与此同时，她身上的钱将会减少 $a_i$ 元；若当前店铺的爆款包包价格高于她身上的钱，则她就逛逛，不买。

对于每一次桃子来逛街的事件，你需要回答出她每次都买了多少只包包。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$，以一个空格分隔（$1 \le n,q \le 2 \cdot 10^5$），分别表示店铺的数量和事件数。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$，两两之间以一个空格分隔，分别表示一开始每一个店铺的爆款包包的价格。

接下来 $q$ 行，每行包含三个整数 $t,x,y(1 \le t \le 2, 1 \le x \le n, 1 \le y \le 10^9)$，两两之间以一个空格分隔，表示一个时间的相关信息，含义如题目描述所示。

数据保证至少有一个事件类型为 $2$（即 $t=2$）。

输出格式

对于每一次事件 $2$，输出一行一个整数，表示桃子这次购物购买的包包的数量。

样例

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

8
3
6
2

样例解释

• 第 $1$ 个事件中桃子在第 $3$ 到 $10$ 个店铺都买了爆款包包；
• 第 $2$ 个事件中桃子在第 $4,9,10$ 个店铺买了爆款包包；
• 第 $3$ 个事件发生后各店铺爆款包包的价格变成了 $\{10,10,10,6,6,5,5,5,3,1\}$；
• 第 $4$ 个事件中桃子在第 $2,3,4,5,9,10$ 个店铺买了爆款包包；
• 第 $5$ 个事件发生后各店铺爆款包包的价格变成了 $\{10,10,10,7,6,5,5,5,3,1\}$；
• 第 $6$ 个事件中桃子在第 $2,4$ 个店铺买了爆款包包。

数据范围

• 对于 $5\%$ 的数据，$n,q \le 10$；
• 对于 $10\%$ 的数据，$n,q \le 1000$；
• 对于 $20\%$ 的数据，$n,q \le 10000$；
• 对于 $50\%$ 的数据，$n,q \le 10^5$；
• 对于 $100\%$ 的数据，$1 \le n,q \le 2 \cdot 10^5,1 \le t \le 2, 1 \le x \le n, 1 \le a_i,y \le 10^9$。