区間等差数列加算

2 secs 1024 MB
Today03's icon Today03

問題文

長さ NN の数列 AA があります。初め、 AA の要素は全て 00 です。また、 AA は 0-indexed とします。

以下の QQ 個のクエリを処理したのち、最終的な AA の要素を空白区切りで 1 行に出力し、改行してください。

l, r, s, t : li<rl\le i \lt r を満たす ii について、 AiA_is+(il)×ts+(i-l)\times t を加算する。

制約

  • N,Q2×105N,Q \le 2\times 10^5

  • 0l<rN(1iQ)0\le l\lt r\le N (1\le i \le Q)

  • 107s107(1iQ)-10^7\le s \le 10^7 (1\le i \le Q)

  • 107t107(1iQ)-10^7\le t \le 10^7 (1\le i \le Q)

  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。

N Q
l_1 r_1 s_1 t_1
l_2 r_2 s_2 t_2
...
l_Q r_Q s_Q t_Q

出力

クエリを全て処理した後の AA の要素を空白区切りで 1 行に出力し、改行してください。

サンプル

入力
5 1
0 5 0 1
出力
0 1 2 3 4
入力
3 2
0 1 10000 0
0 1 10000 0
出力
20000 0 0
入力
10 5
0 9 -4 1
0 5 2 2
4 8 1 5
7 10 4 -3
3 7 4 4
出力
-2 1 4 11 19 19 29 23 5 -2

提出


Go (1.21)