描述

格式

输入格式

第一行包含一个整数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