#6109. 「2017 山东二轮集训 Day4」增添

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一个长度为 n 的序列,要求支持三种操作:

  • 1 l r x [l, r] 中的数增加 x ,保证 x \leq 10000
  • 2 l r x [l, l + x] 中的数对应替换 [r, r + x] 中的数;
  • 3 l r [l, r] 中所有数的和。

输入格式

第一行两个正整数 n, m 表示序列长度和操作数。
第二行 n 个正整数表示初始序列中的数,保证每个数 \leq 10000
接下来 m 行,每行三或四个整数,对应一个操作。
保证操作的区间合法且为 [1, n] 的子集。

输出格式

对每个操作三,单独输出一行表示答案。

样例

样例输入

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

样例输出

18
13

数据范围与提示

n \leq 100000, m \leq 100000