AT_abc455_f [ABC455F] Merge Slimes 2

長さ $ N $ の非負整数列 $ A $ があり、最初はすべての要素が $ 0 $ です。 $ Q $ 個のクエリが与えられるので順に処理してください。 $ q $ 番目のクエリでは $ 1 \leq l_q \leq r_q \leq N $ を満たす整数 $ l_q,r_q $ と正整数 $ a_q $ が与えられるので、以下を順に行ってください。 - $ A_{l_q}, A_{{l_q}+1}, \dots, A_{r_q} $ に $ a_q $ を足す。 - その後、 $ M=r_q-l_q+1, \; B=(B_1,B_2,\dots,B_M)=(A_{l_q}, A_{l_q+1}, \dots, A_{r_q}) $ として、以下の問題の答えを求める。 > $ M $ 個のスライム $ 1,2,\dots,M $ があって、 $ m $ 個目のスライムの重さは $ B_m $ です。 > $ 2 $ 個のスライムを選び、合成させるという操作を $ M-1 $ 回繰り返します。 > 重さが $ x,y $ のスライムを合成させると重さ $ x+y $ のスライムが出現し、元の $ 2 $ 個のスライムは消えます。このとき $ x \times y $ のコストがかかります。 > $ M-1 $ 回の操作のコストの総和としてあり得る値の最小値を $ 998244353 $ で割った余りを求めてください。 各クエリでの $ A $ に対する変更内容はその後にも引き継がれることに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ l_1 $ $ r_1 $ $ a_1 $ $ l_2 $ $ r_2 $ $ a_2 $ $ \vdots $ $ l_Q $ $ r_Q $ $ a_Q $

答えを合計 $ Q $ 行で出力せよ。 $ q $ 行目には、 $ q $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリの後、 $ A=(22,22,22,0,0) $ となり、 $ B=(22,22,22) $ です。 $ 1 $ 回目に $ 1 $ つ目のスライムと $ 3 $ つ目のスライムを合成すると、そのコストは $ 22 \times 22=484 $ です。次に残った $ 2 $ つのスライムを合成するとそのコストは $ 22 \times 44=968 $ です。このときコストの合計は $ 484+968=1452 $ です。また、コストの合計をこれよりも小さくすることはできません。 $ 2 $ 番目のクエリの後、 $ A=(22,22,35,13,0) $ となり、 $ B=(35,13) $ です。求める答えは $ 35 \times 13 = 455 $ です。 ### Constraints - $ 1 \leq N \leq 10^5 $ - $ 1 \leq Q \leq 10^5 $ - $ 1 \leq l_q \leq r_q \leq N $ - $ 1 \leq a_q \leq 10^9 $ - 入力はすべて整数