你的朋友正在经营一家花店。为了为下一个假期做好准备(与往常一样,销售量会猛增),她要求您为她编写一个特殊程序,以帮助分析她所拥有的股票。
她可以订购 $$$n$$$ 种不同类型的鲜花,并且 $$$i$$$ 类型的每朵花的价格为 $$$w_i$$$。上个假期非常成功,她卖掉了所有的花,所以现在她所有的库存都空了。
从此时起,她开始了订购和销售鲜花的日常操作,同时尝试分析她手头的物品。所有这些都可以表示为三种类型的 $$$m$$$ 查询:
- “$$$1$$$ $$$i$$$ $$$c$$$”——她买了 $$$c$$$ 类型的花 $$$i$$$;
- “$$$2$$$ $$$i$$$ $$$c$$$”——她处理掉了$$$c$$$类型的$$$i$$$花;
- “$$$3$$$ $$$l$$$ $$$r$$$ $$$k$$$"—仅使用 $$$l、l + 1、\dots、r$$$ 类型的花朵,她可以制作多少种花束,总成本不超过 $$$k$$$。为简单起见,您可以认为花束是花朵的多重集,如果两束花束作为多重集不同,则它们是不同的。一束花的成本是它所拥有的所有花朵的总和。
帮助您的朋友编写可以处理所有这些查询的程序。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 1000$$$; $$$1 \le m \le 1000$$$) — 花种数量和查询数量。
第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 1000$$$) — 每种类型一朵花的成本。
接下来的 $$$m$$$ 行包含查询 - 每行一个。每个查询都具有以下三种类型之一:
- $$$1$$$ $$$i$$$ $$$c$$$ ($$$1 \le i \le n$$$; $$$1 \le c \le 5000$$$);
- $$$2$$$ $$$i$$$ $$$c$$$ ($$$1 \le i \le n$$$; $$$1 \le c \le 5000$$$)。保证此时至少有$$$c$$$类型为$$$i$$$的花;
- $$$3$$$ $$$l$$$ $$$r$$$ $$$k$$$ ($$$1 \le l \le r \le n$$$; $$$1 \le k \le 5000$$$)
保证每次查询后所有库存鲜花的总成本不超过$$$5000$$$。
输出
对于第三种类型的每个查询,打印她仅使用 $$$l、l + 1、\dots、r$$$ 类型的花可以制作多少种花束,总成本不超过 $$$k$$$。由于答案可能太大,请打印 $$$998\,244\,353$$$ 模。
示例
输入 #1
5 12 1 2 3 2 1 1 1 5 1 2 3 1 3 1 3 1 5 10 3 4 5 100 1 4 4 1 5 1 3 2 5 7 3 1 1 3 3 1 5 100 2 1 5 3 1 5 100
输出 #1
40 0 28 3 479 79