问题描述

给定一个长度为 n 的数组 a，有 q 次询问，l，r,m分别代表l起点，r为终点，m对每个数进行加处理，继续k次，每次询问数组 a 在区间 [l, r] 的和。

格式

输入

第一行一个整数 n，(1 ≤ n ≤ 10^5) 第二行 n 个整数表示数组 a，(-10^9 ≤ ai ≤ 10^9) 第三行一个整数 q，(1 ≤ q ≤ 10^5) 接下来 q 行，每行三个整数 li, ri，m(1 ≤ li ≤ ri ≤ n) 接下来询问k次 接下来 k行，每行三个整数 li, ri(1 ≤ li ≤ ri ≤ n)

输出

每一行对应每一个样例，输出一个整数表示答案。

样例

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

2
-1

提示

数据范围、额外说明、样例说明等等