Flower Shop
Contest: Kotlin Heroes: Episode 6
Difficulty rating: 3100
Tags: *special, data structures, fft, math

Your 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 format:
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 format:
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$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

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

Example output:
40
0
28
3
479
79

Editorial:
This task is a some variation of knapsack problem, so the solution is either based on dp with weight in the state or it uses multiplication of polynomials. The second variant is our choice.
Suppose, there are $$$cur_i$$$ flowers of type $$$i$$$ at this moment. Let's make for each flower type a polynomial $$$P_i = c_0 + c_1 x + c_2 x^2 + \dots + c_{(\mathit{MX} - 1)} x^{(\mathit{MX} - 1)}$$$ where $$$\mathit{MX} = 2^{13}$$$ and $$$c_j$$$ is $$$1$$$ if $$$j \bmod w_i = 0$$$ and $$$j \le cur_i \cdot w_i$$$ and $$$0$$$ otherwise.
Now, if we calculate the product of polynomials $$$P_l \cdot P_{l + 1} \cdot \ldots \cdot P_r$$$ we'll get the polynomial such that $$$c_j$$$ is exactly the number of different bouquets with cost $$$j$$$ we can make using flowers of types from $$$l$$$ to $$$r$$$.
Note that the degree of polynomial product is less than $$$\mathit{MX}$$$. So we can, for example, write divide-and-conquer with integer FFT (NTT) (since module is equal to $$$998\,244\,353$$$) but it has complexity $$$O(\mathit{MX} \cdot \log{\mathit{MX}} \cdot \log{n})$$$ and, most likely, doesn't pass.
But since all products have degree less than $$$\mathit{MX}$$$, we can keep all polynomials as polynomials of degree $$$\mathit{MX} - 1$$$ and in transformed form (using FFT). Then, to restore the answer, we need to get products of each coefficient $$$c_i$$$ independently and after that transform it back.
Note that to get products of each coefficient $$$c_i$$$ on segment $$$[l, r]$$$ we can use $$$\mathit{MX}$$$ Segment Trees and get all products in $$$O(\mathit{MX} \log{n})$$$. So, the complexity of query of the third type is $$$O(\mathit{MX} (\log{n} + \log{\mathit{MX}}))$$$.
Processing queries of the first and the second types is straightforward: we can manually calculate new polynomial $$$P_i$$$, transform it and update all Segment Trees also in $$$O(\mathit{MX} (\log{n} + \log{\mathit{MX}}))$$$ time.
The total complexity is $$$O(m \cdot \mathit{MX} \cdot (\log{n} + \log{\mathit{MX}}))$$$.