← 返回题目列表

Codeforces · 1488/J

J. 花店

中文机器翻译题面 查看原题

你的朋友正在经营一家花店。为了为下一个假期做好准备(与往常一样,销售量会猛增),她要求您为她编写一个特殊程序,以帮助分析她所拥有的股票。

她可以订购 $$$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