A. 咕咕咕

内存限制:128 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

出题人作业写不完了,只好咕掉题目背景了

现在给你一个长度为 nnn 的序列 a1,a2,,an 你需要支持这两种操作

  • 第一种操作的格式是 111 xxx yyy 表示 在 xxx 这个位置上加上 yyy

  • 第二种操作的格式是 222 lll rrr kkk 表示求出 vvv

v=∑i=lr(ai+k)3 v = \sum_{i = l}^{r} {(a_i + k)} ^ 3v=i=lr(ai+k)3

输入格式

第一行 nnn mmm :

nnn 表示序列长度, mmm 表示操作次数

第二行 nnn 个数 为 a1,a2,,an

接下来 mmm 行 :

每行都是两种操作中的一种

输出格式

对于每个操作 222 每行一个输出

样例

输入

5 5
3 2 1 3 1 
2 1 5 0
1 5 1
2 2 4 0
2 1 4 0
2 4 5 -1

输出

64
36
63
9

数据范围与提示

  • 30%30\%30% 的数据 000 <=<=<= n,mn, mn,m <=<=<= 100100100

  • 100%100\%100% 的数据 000 <<< n,mn, mn,m <<< 1,000,0001,000, 0001,000,000

最初 ∣ai∣|a_i|ai <=<=<= 100100100

对于每操作 111 保证 :

  • 111 <=<=<= xxx <=<=<= nnn
  • ∣y∣|y|y <= 200200200

对于每种操作 222 保证 :

  • 111 <=<=<= lll <=<=<= rrr <=<=<= nnn
  • kkk <=<=<= 200200200