E2. Amanojaku and Sequence (Hard 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 hard version of the problem. The difference between the versions is that in this version, $$$1\le q \le 3\cdot 10^5$$$ and $$$1\le\mathrm{op}\le2$$$. 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 two types:

  • Given two integers $$$p$$$ and $$$v$$$, set $$$a_p$$$ to $$$v$$$.
  • 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$$$, $$$1\leq q\leq 3\cdot 10^5$$$).

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 one of the following format. The first integer $$$\textrm{op}$$$ is $$$1$$$ or $$$2$$$.

  • $$$1\,p\,v$$$: set $$$a_p$$$ to $$$v$$$ ($$$1\leq p\leq n$$$, $$$-1\leq v\leq 10^6$$$);
  • $$$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$$$.

It is guaranteed that the sum of $$$q$$$ 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
2
5 7
4 -1 7 6 -1
2 2 2 2
1 3 8
2 3 3 0
2 4 5 8
1 5 7
2 3 5 21
2 3 5 22
4 6
-1 -1 -1 -1
2 1 1 4
2 1 2 5
2 1 3 6
2 1 4 7
1 3 3
2 1 4 5
Output
4
0
100
701
0
16
205
1736
12180
286
Note

In the first test case:

For the first query, $$$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$$$.

For the fourth query, $$$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 second test case:

For the second query, 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$$$.