Note

The execution time limit for this problem is 6000[ms]. Since the time limit is tight, using a fast language and implementation is recommended.

For reference, the writer's solution takes 163[ms] in C++ and 4309[ms] in PyPy3, and exceeds 10000[ms] in Python3, that is, TLE.

Problem Statement

At the beginning of the input, $2$ positive integers $N, Q$ and a sequence $A$ of non-negative integers of length $N$ are given.

Process the $Q$ queries described below in the order given in the input, updating $A$.

Let $n$ be the length of $A$ at the time a query is given. Each query is a tuple $(i,x,\ell,r)$ of a positive integer $i$ not exceeding $n$, a non-negative integer $x$, and positive integers $\ell,r$ satisfying $1 \leq \ell \leq r \leq n + 1$.

A query $(i,x,\ell,r)$ is processed as follows.

1. First, update $A$ by inserting $x$ immediately after the $i$-th element of $A$.
2. Next, compute the range sum $\sum_{j=\ell}^{r} A_j$ for the updated $A$. (Hereafter, this value is called the answer to this query.)

Here, for $A$ and each positive integer $i$ not exceeding its length, $A_i$ denotes the $i$-th element of $A$.

Input

For each positive integer $q$ not exceeding $Q$, the $q$-th query $(i,x,\ell,r)$ is written as $(i_q,x_q,\ell_q,r_q)$.

The input is given from standard input in $2 + Q$ lines in the following format:

• The $1$st line contains $N, Q$, separated by a single space.
• The $2$nd line contains $A_i$ for each positive integer $i$ not exceeding $N$, in increasing order of $i$, separated by single spaces.
• For each positive integer $q$ not exceeding $Q$, line $2 + q$ contains $i_q,x_q,\ell_q,r_q$, separated by single spaces.

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

Constraints

The input satisfies the following constraints:

• $N$ is an integer satisfying $1 \leq N \leq 6 \times 10^4$.
• $Q$ is an integer satisfying $1 \leq Q \leq 2 \times 10^4$.
• For any positive integer $i$ not exceeding $N$, $A_i$ is a non-negative integer satisfying $0 \leq A_i \leq 10^4$.
• For any positive integer $q$ not exceeding $Q$,
• $i_q$ is an integer satisfying $1 \leq i \leq N + q - 1$.
• $x_q$ is an integer satisfying $0 \leq x \leq 10^4$.
• $\ell_q, r_q$ are integers satisfying $1 \leq \ell_q \leq r_q \leq N + q$.

Output

For each positive integer $q$ not exceeding $Q$, output the answer to the $q$-th query on the $q$-th line.

Print a newline at the end.

Sample

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