序列杀手

序列杀手

描述

格式

输入格式

第一行包含一个整数N,表示序列a与f有多少个数。
第二行包含N个整数,表示序列a。
接下来包含N行,每一行包含两个整数,分别是li与ri,意义已在上面描述。
接下来包含一个整数M,表示有多少个操作。
接下来包含M行,每一行包含三个整数opt,x,y。若opt为1,那么表示将a序列中第x个数改为y。若opt为2,那么表示询问f序列中区间[x,y]的总和。

输出格式

对于每一个opt为2的操作,输出所要求的总和。

样例

样例输入

5
1 2 3 4 5
1 3
2 5
4 5
3 5
1 2
4
2 1 4
1 3 7
2 1 4
2 3 5

样例输出

41
53
28

限制

每个测试点1s,256MB

提示

数据范围:
1 ≤ N ≤ 10^5
1 ≤ ai ≤ 10^8
1 ≤ li ≤ N
ri ≤ ri ≤ N
1 ≤ M ≤ 10^5

对于10%的数据,满足1 ≤ N ≤ 10^3。
对于另外10%的数据,满足ri-li<=10。
请注意本题数据较大时限较小,请使用快速的读入输出方式,尽量的避免常数大的算法。

Source

KEKE_046 && Bill_Yang 搬运自CodeChef FNCS