给定数字N和Q，N表示有一个长度为N的数字序列，Q表示要进行Q次操作。
操作类型如下：

INPUT
第一行两个整数 N and Q (1 ≤ N, Q ≤ 100 000), 表示数字序列开始的长度和操作的次数。
接下来一行N个非负数。每个数小于等于100000用空格分隔.
执下来Q行，每行一个操作。所有操作中 1 ≤ X ≤ 100, 1 ≤ A ≤ B ≤ 当前最长长度,且 1 ≤ C ≤ 当前最长长度加1.
输出：
对于每一个操作类型为4的给出一个答案，各占一行。一些答案超过32位整数。.
SAMPLE TESTS
input
5 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5
output
4
0
25

input
1 7
100
3 1 17
3 2 27
3 4 37
4 1 1
4 2 2
4 3 3
4 4 4
output
17
27
100
37