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. 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 integer