The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 6:

- Kotlin 1.4.31

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
J. Flower Shop

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYour friend is running a flower shop. In order to be prepared for the next holidays (when, as usual, sales skyrocket) she asked you to write her a special program that will help to analyze the stocks she has.

There are $$$n$$$ different types of flowers she can order and each flower of the type $$$i$$$ costs $$$w_i$$$. The last holidays were a great success, she sold all flowers she had, so right now all her stocks are empty.

From this point, she starts routine operations of ordering and selling flowers, while trying to analyze what she has at hand. All of this can be represented as $$$m$$$ queries of three types:

- "$$$1$$$ $$$i$$$ $$$c$$$" — she bought $$$c$$$ flowers of type $$$i$$$;
- "$$$2$$$ $$$i$$$ $$$c$$$" — she disposed of $$$c$$$ flowers of type $$$i$$$;
- "$$$3$$$ $$$l$$$ $$$r$$$ $$$k$$$" — how many variants of bouquets she can make using only flowers of types $$$l, l + 1, \dots, r$$$ with the total cost no more than $$$k$$$. For simplicity, you can think that a bouquet is a multiset of flowers, and two bouquets are different if they are different as multisets. The cost of a bouquet is the sum of all flowers it has.

Help your friend and write the program that can process all these queries.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 1000$$$; $$$1 \le m \le 1000$$$) — the number of flower types and the number of queries.

The second line contains $$$n$$$ integers $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 1000$$$) — the cost of one flower of each type.

The next $$$m$$$ lines contains queries — one per line. Each query has one of three types:

- $$$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$$$). It's guaranteed that there are at least $$$c$$$ flowers of type $$$i$$$ at this moment;
- $$$3$$$ $$$l$$$ $$$r$$$ $$$k$$$ ($$$1 \le l \le r \le n$$$; $$$1 \le k \le 5000$$$)

It's guaranteed that the total cost of all flowers in stock after each query doesn't exceed $$$5000$$$.

Output

For each query of the third type, print how many variants of bouquets she can make using only flowers of types $$$l, l + 1, \dots, r$$$ with the total cost no more than $$$k$$$. Since the answer may be too large, print it modulo $$$998\,244\,353$$$.

Example

Input

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

Output

40 0 28 3 479 79

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/22/2022 01:49:19 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|