E1. Amanojaku and Sequence (Easy Version)
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Tinkerbell of Inequality
— Taboo Japan Disentanglement

This is the easy version of the problem. The difference between the versions is that in this version, $$$q=1$$$ and $$$\mathrm{op}=2$$$. You can hack only if you solved all versions of this problem.

For a sequence $$$s$$$, let $$$|s|$$$ denote its length.

For a non-negative integer sequence $$$c$$$, define $$$f(c)$$$ as the sum of the squares of its prefix sums: $$$$$$ f(c)=\sum_{i=1}^{|c|}\left(\sum_{j=1}^{i} c_j\right)^2. $$$$$$

Now define $$$g(b,m)$$$ as follows.

Let $$$b$$$ be an integer sequence such that $$$b_i\ge -1$$$ for every $$$i$$$, and let $$$m$$$ be a non-negative integer. A non-negative integer sequence $$$c$$$ is called valid for $$$(b,m)$$$ if all of the following conditions hold:

  • $$$|c|=|b|$$$;
  • $$$\sum_{i=1}^{|c|} c_i=m$$$;
  • for every $$$1\le i\le |b|$$$, if $$$b_i\ge 0$$$, then $$$c_i=b_i$$$; otherwise, if $$$b_i=-1$$$, then $$$c_i$$$ may be any non-negative integer.

The value $$$g(b,m)$$$ is defined as the sum of $$$f(c)$$$ over all valid sequences $$$c$$$ for $$$(b,m)$$$. If there is no such sequence, then $$$g(b,m)=0$$$.

You are given an array $$$a$$$ of length $$$n$$$, where $$$a_i\ge -1$$$, and $$$q$$$ queries of the following one type:

  • Given three integers $$$l$$$, $$$r$$$, and $$$m$$$, compute $$$g([a_l,a_{l+1},\ldots,a_r],m)$$$ modulo $$$998\,244\,353$$$, where $$$[a_l,a_{l+1},\ldots,a_r]$$$ denotes the subarray$$$^{\text{∗}}$$$ of $$$a$$$ from position $$$l$$$ to position $$$r$$$.

$$$^{\text{∗}}$$$An array $$$a$$$ is a subarray of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

For each test case, the first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n\leq 3\cdot 10^5$$$, $$$q=1$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-1\leq a_i\leq 10^6$$$).

Then $$$q$$$ lines follow. Each line describes a query in the following format. The first integer $$$\textrm{op}$$$ is $$$2$$$.

  • $$$2\,l\,r\,m$$$: compute $$$g([a_l,a_{l+1},\ldots,a_r],m)$$$ modulo $$$998\,244\,353$$$ ($$$1\leq l\leq r\leq n$$$, $$$0\leq m\leq 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.

Output

For each test case, for every query of the second type, output the value of $$$g([a_l,a_{l+1},\ldots,a_r],m)$$$ modulo $$$998\,244\,353$$$ on a line.

Example
Input
10
5 1
4 -1 7 6 -1
2 2 2 2
5 1
4 -1 8 6 -1
2 3 3 0
5 1
4 -1 8 6 -1
2 4 5 8
5 1
4 -1 8 6 7
2 3 5 21
5 1
4 -1 8 6 7
2 3 5 22
4 1
-1 -1 -1 -1
2 1 1 4
4 1
-1 -1 -1 -1
2 1 2 5
4 1
-1 -1 -1 -1
2 1 3 6
4 1
-1 -1 -1 -1
2 1 4 7
4 1
-1 -1 3 -1
2 1 4 5
Output
4
0
100
701
0
16
205
1736
12180
286
Note

In the first test case:

$$$l=r=2$$$ and $$$m=2$$$. The subarray is $$$[a_2]=[-1]$$$, so the only valid sequence is $$$c=[2]$$$. Thus, the answer is $$$2^2=4$$$.

In the third test case:

$$$l=4$$$, $$$r=5$$$, and $$$m=8$$$. The subarray is $$$[a_4,a_5]=[6,-1]$$$. Since $$$c_1$$$ is fixed at $$$6$$$ and $$$c_1+c_2=m$$$, we obtain $$$c=[6,2]$$$. The prefix sums are $$$6$$$ and $$$8$$$, giving $$$$$$ f(c)=6^2+(6+2)^2=36+64=100. $$$$$$

In the seventh test case:

The subarray is $$$[a_1,a_2]=[-1,-1]$$$. All valid sequences satisfy $$$c_1+c_2=5$$$ with $$$c_1,c_2\ge 0$$$, namely $$$[0,5],[1,4],\ldots,[5,0]$$$. Summing $$$f(c)$$$ over all such sequences yields $$$205$$$.