[ABC357F] Two Sequence Queries

给定两个长度为 $N$ 的序列 $A_N, B_N$，现在需要维护 $Q$ 次以下三种操作： - `1 l r x` 将 $A_l, A_{l + 1}, \cdots, A_r$ 全部加 $x$； - `2 l r x` 将 $B_l, B_{l + 1}, \cdots, B_r$ 全部加 $x$； - `3 l r` 求 $\sum_{i = l}^r A_i \times B_i \bmod 998244353$。

[problemUrl]: https://atcoder.jp/contests/abc357/tasks/abc357_f 長さ $ N $ の数列 $ A=(A_1,A_2,\ldots,A_N) $, $ B=(B_1,B_2,\ldots,B_N) $ が与えられます。 $ Q $ 個のクエリが与えられるので、順に処理してください。 クエリは次の $ 3 $ 種類です。 - `1 l r x` : $ A_l,\ A_{l+1},\ \ldots,\ A_r $ に $ x $ を加える。 - `2 l r x` : $ B_l,\ B_{l+1},\ \ldots,\ B_r $ に $ x $ を加える。 - `3 l r` : $ \displaystyle\sum_{i=l}^r\ (A_i\times\ B_i) $ を $ 998244353 $ で割った余りを出力する。

入力は以下の形式で標準入力から与えられる。ここで、$ \mathrm{query}_i $ $ (1\leq\ i\leq\ Q) $ は $ i $ 番目に処理するクエリである。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下のいずれかの形式で与えられる。 > $ 1 $ $ l $ $ r $ $ x $ > $ 2 $ $ l $ $ r $ $ x $ > $ 3 $ $ l $ $ r $

$ 3 $ 種類目のクエリが $ K $ 個あるとき、$ K $ 行出力せよ。 $ i $ 行目 ($ 1\leq\ i\leq\ K $) には、$ i $ 個目の $ 3 $ 種類目のクエリに対する出力を出力せよ。

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

16
25
84

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

716070898
151723988

### 制約 - $ 1\leq\ N,Q\leq\ 2\times\ 10^5 $ - $ 0\leq\ A_i,B_i\leq\ 10^9 $ - $ 1\leq\ l\leq\ r\leq\ N $ - $ 1\leq\ x\leq\ 10^9 $ - 入力はすべて整数 - $ 3 $ 種類目のクエリが $ 1 $ つ以上存在する。 ### Sample Explanation 1 最初、$ A=(1,3,5,6,8) $, $ B=(3,1,2,1,2) $ です。クエリは次の順で処理されます。 - $ 1 $ 個目のクエリでは $ (1\times\ 3)+(3\times\ 1)+(5\times\ 2)=16 $ を $ 998244353 $ で割った余りである $ 16 $ を出力します。 - $ 2 $ 個目のクエリでは $ A_2,A_3,A_4,A_5 $ に $ 3 $ を加えます。$ A=(1,6,8,9,11) $ となります。 - $ 3 $ 個目のクエリでは $ (1\times\ 3)+(6\times\ 1)+(8\times\ 2)=25 $ を $ 998244353 $ で割った余りである $ 25 $ を出力します。 - $ 4 $ 個目のクエリでは $ A_1,A_2,A_3 $ に $ 1 $ を加えます。$ A=(2,7,9,9,11) $ となります。 - $ 5 $ 個目のクエリでは $ B_5 $ に $ 2 $ を加えます。$ B=(3,1,2,1,4) $ となります。 - $ 6 $ 個目のクエリでは $ (2\times\ 3)+(7\times\ 1)+(9\times\ 2)+(9\times\ 1)+(11\times\ 4)=84 $ を $ 998244353 $ で割った余りである $ 84 $ を出力します。 よって、$ 1 $, $ 2 $, $ 3 $ 行目にはそれぞれ $ 16 $, $ 25 $, $ 84 $ を出力します。 ### Sample Explanation 2 $ 3 $ 種類目のクエリでは $ 998244353 $ で割った余りを出力することに注意してください。