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 $A$ with $n$ numbers and he keeps a copy of the initial value of array $A$ as $A’(A_i’=A_i)$. Then he makes $m$ operations on it.

There are three types of operations:

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

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

输入格式

The first line contains two numbers $1 \leq n,m \leq 2 \times 10^5$.

The second line contains $n$ numbers $A_i$. Then $m$ lines follow, each line describe an operation.

It is guaranteed that $1 \leq k \lt l,0 \leq Ai \leq 10^9$

输出格式

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 奖励。

创建: 2 年,9 月前.

修改: 2 年,9 月前.

最后提交: 2 年,9 月前.

来源: 2017 Multi-University Training 5

题目标签