3413. Rikka with Sequence

单点时限: 5.5 sec

内存限制: 2048 MB

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has an array with numbers and he keeps a copy of the initial value of array as . Then he makes operations on it.

There are three types of operations:

  • 1 l r: Yuta wants Rikka to sum up for all in .
  • 2 l r k: Yuta runs the C++ code for (int i=l;i<=r;i++) A[i]=A[i-k] on sequence . (The pascal version of the code snippet is for i:=l to r do A[i]:=A[i-k]).
  • 3 l r: Yuta changes back to , for all .

It is too difficult for Rikka. Can you help her?

输入格式

The first line contains two numbers .

The second line contains numbers . Then lines follow, each line describe an operation.

It is guaranteed that

输出格式

For each query, print a single line with a single number – the answer.

样例

Input
5 7
1 2 3 4 5
1 1 5
2 3 4 1
1 1 5
2 3 4 2
1 1 5
3 1 5
1 1 5
Output
15
12
11
15

提示

吉老师表示不想卡空间,奈何 HDU 内存限制不支持。所以移植到 EOJ 给了大家 2G 内存。

2 人解决,3 人已尝试。

3 份提交通过,共有 6 份提交。

8.6 EMB 奖励。

创建: 1 年,8 月前.

修改: 1 年,8 月前.

最后提交: 1 年,8 月前.

来源: 2017 Multi-University Training 5

题目标签