注意

この問題の実行時間制限は6000[ms]です。実行時間が厳しいので高速な言語・処理系の仕様を推奨します。

参考までにwriter解の実行時間はc++で163[ms]、PyPy3で4309[ms]、Python3で10000[ms]超すなわち TLE となります。

問題文

入力の最初に $2$ 個の正整数 $N, Q$ と、長さ $N$ の非負整数列 $A$ が与えられます。

以下で説明する $Q$ 個のクエリを入力で与えられた順に処理することで $A$ を更新してください。

各クエリは、それが与えられた時点での $A$ の長さを $n$ と置いた時、$n$ 以下の正整数 $i$ と非負整数 $x$ と$1 \leq \ell \leq r \leq n + 1$ を満たす正整数 $\ell,r$ の組 $(i,x,\ell,r)$ です。

クエリ $(i,x,\ell,r)$ は以下のように処理します。

1. まず $A$ の $i$ 個目の成分の直後に $x$ を挿入することで $A$ を更新する。
2. 次に更新後の $A$ に対し、区間和 $\sum_{j=\ell}^{r} A_j$ を計算する。（以下、この値をこのクエリに対する回答と呼ぶ）

ただし $A$ とその長さ以下の各正整数 $i$ に対し、$A_i$ で $A$ の $i$ 個目の成分を表します。

入力

$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリ $(i,x,\ell,r)$ を $(i_q,x_q,\ell_q,r_q)$ と書き表します。

この時、入力は以下の形式で標準入力から $2 + Q$ 行で与えられます：

• $1$ 行目に $N, Q$ が半角空白区切りで与えられます。
• $2$ 行目に $N$ 以下の各正整数 $i$ に対する $A_i$ が $i$ の小さい順に半角空白区切りで与えられます。
• $Q$ 以下の各正整数 $q$ に対し、$2 + q$ 行目に $i_q,x_q,\ell_q,r_q$ が半角空白区切りで与えられます。

$N$ $Q$
$A_1$ $\cdots$ $A_N$
$i_1$ $x_1$ $\ell_1$ $r_1$
$\vdots$
$i_Q$ $x_Q$ $\ell_Q$ $r_Q$

制約

入力は以下の制約を満たします：

• $N$ は $1 \leq N \leq 6 \times 10^4$ を満たす整数である。
• $Q$ は $1 \leq Q \leq 2 \times 10^4$ を満たす整数である。
• $N$ 以下の任意の正整数 $i$ に対し、$A_i$ は $0 \leq A_i \leq 10^4$ を満たす正整数である。
• $Q$ 以下の任意の正整数 $q$ に対し、
• $i_q$ は $1 \leq i \leq N + q - 1$ を満たす整数である。
• $x_q$ は $0 \leq x \leq 10^4$ を満たす整数である。
• $\ell_q, r_q$ は $1 \leq \ell_q \leq r_q \leq N + q$ を満たす整数である。

出力

$Q$ 以下の各正整数 $q$ に対し、$q$ 行目に $q$ 個目のクエリに対する回答を出力してください。

最後に改行してください。

サンプル

1 1
0
1 1 1 2

1

1 2
1
1 2 2 2
2 3 1 3

2
6

2 2
0 1
1 2 2 3
2 3 1 4

3
6