给定一个长度为 $n$ 的序列 $A_{0,1}, A_{0,2}, \cdots, A_{0,n}$。初始时，整数 $c$ 的值为 $0$。你需要处理以下 $m$ 次操作：

• 1 l r x：
  • 对于每个 $1 \le i \le n$，令 $A_{c+1,i} \leftarrow A_{c,i}$。
  • 对于每个 $l \leq i \leq r$，令 $A_{c+1,i} \leftarrow A_{c+1,i} + x$。
  • 令 $c \leftarrow c+1$。
• 2 l r：输出 $A_i$ 在历史时刻的总和，其中 $l \leq i \leq r$。即输出 $\sum_{k=0}^c \sum_{i=l}^r A_{k,i}$。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示序列的长度和操作次数。

第二行包含 $n$ 个整数 $A_{0,1}, A_{0,2}, \cdots, A_{0,n}$，描述了初始时刻序列 $A$ 的值。

接下来 $m$ 行，每行描述一个操作。

输出格式

对于每个类型为 2 的查询，输出一行，包含一个整数，表示答案。

样例

样例输入 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

样例输出 1

6
21
50

样例输入 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

样例输出 2

-2
0
25

子任务

保证 $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$。

• 子任务 1（10 分）：$1 \leq n,m \leq 5000$
• 子任务 2（30 分）：对于类型 1 的查询，满足 $l = r$
• 子任务 3（30 分）：对于类型 2 的查询，满足 $l = r$
• 子任务 4（30 分）：无附加限制