Given a sequence $A_{0,1}, A_{0,2}, \cdots, A_{0,n}$ with the length $n$. Initially, the value of the integer $c$ is $0$. You need to process the following $m$ queries:

• 1 l r x:
  • For each $1 \le i \le n$, Let $A_{c+1,i} \leftarrow A_{c,i}$.
  • For each $l \leq i \leq r$, let $A_{c+1,i} \leftarrow A_{c+1,i} + x$.
  • Let $c \leftarrow c+1$.
• 2 l r: Print the sum of the historical value of $A_i$ when $l \leq i \leq r$. That is, print $\sum_{k=0}^c \sum_{i=l}^r A_{k,i}$.

Input

The first line of the input contains two integers $n$ and $m$ - the length of the sequence and the number of the operations.

The next line of the input contains $n$ integers $A_{0,1}, A_{0,2}, \cdots, A_{0,n}$, describes the sequence $A$ at the initial time.

The next $m$ lines of the input describe one query per line.

Output

For each query of type 2, you need to output a line with a single integer indicating the answer.

Samples

Input 1

1 9
2
1 1 1 2
2 1 1
1 1 1 3
1 1 1 1
2 1 1
1 1 1 4
1 1 1 -2
1 1 1 -3
2 1 1

Output 1

6
21
50

Input 2

6 8
5 -2 4 -7 3 -5
2 2 5
1 1 4 -2
1 2 5 3
1 1 3 2
2 1 4
1 2 5 4
1 4 6 3
2 3 6

Output 2

-2
0
25

Scoring

It is guaranteed that $1 \leq n,m \leq 2 \times 10^5, -10^9 \leq A_i \leq 10^9, 1 \leq l \leq r \leq n, -10^9 \leq x \leq 10^9$.

• Subtask 1(10 points): $1 \leq n,m \leq 5000$
• Subtask 2(30 points): for the query of type 1, we have $l = r$.
• Subtask 3(30 points): for the query of type 2, we have $l = r$.
• Subtask 4(30 ponits): no additional constraints.