题目描述

某宝的在线商店目前有 $N$ 件商品，第 $i$ 件商品剩余库存为 $A_i$ 单位。

按顺序处理接下来的 $Q$ 个订单。第 $i$ 个订单如下：

购买区间 $[l_i, r_i]$ 内每种商品 $k_i$ 单位。若某商品库存少于 $k_i$ 单位，则购买其所有剩余库存。请报告该订单中被购买的商品总数（即购买的单位总数）。

注意：对于 $i<Q$，第 $i$ 个订单购买后库存减少，随后再处理第 $i+1$ 个订单。

输入格式

输入共 $Q+3$ 行，每一行的格式如下：

• 第 $1$ 行：一个整数 $N$，表示商品数量。
• 第 $2$ 行：$N$ 个整数，分别是 $A_1,A_2,\dots,A_N$（以空格分隔）。
• 第 $3$ 行：一个整数 $Q$，表示订单数。
• 第 $4$ 行 到 第 $Q+3$ 行：每一行对应一个订单，第 $i$ 行为第 $i$ 个订单的参数 $l_i\ r_i\ k_i$，均为整数，用空格分隔。

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个订单中被购买的商品总数。

样例输入

6
2 6 4 5 7 5
5
1 6 1
3 5 4
4 4 1
2 5 1
1 6 100

样例输出

6
11
0
2
10

说明

样例解释

初始时各商品库存为（按商品编号）：$[2,6,4,5,7,5]$。

• 第 $1$ 个订单：$l_1=1,r_1=6,k_1=1$。每种商品购买 $1$，共购 $6$ 单位。库存变为 $[1,5,3,4,6,4]$。
• 第 $2$ 个订单：$l_2=3,r_2=5,k_2=4$。在区间 $[3,5]$，商品剩余分别为 $3,4,6$，购买量为 $3,4,4$；合计 $11$ 单位。库存变为 $[1,5,0,0,2,4]$。
• 第 $3$ 个订单：$l_3=4,r_3=4,k_3=1$。第 $4$ 件商品库存为 $0$，购买 $0$，合计 $0$。库存不变。
• 第 $4$ 个订单：$l_4=2,r_4=5,k_4=1$。在区间购买量为 $0,1,0,0,1,0$（只列出区间及影响），合计 $2$。库存变为 $[1,4,0,0,1,4]$。
• 第 $5$ 个订单：$l_5=1,r_5=6,k_5=100$。每种商品购买其所有剩余库存，合计 $10$。库存变为全 $0$。

数据范围

• 所有输入值均为整数。
• $1\le N\le 3\times 10^5$。
• $1\le A_i\le 10^{15}$。
• $1\le Q\le 3\times 10^5$。
• $1\le l_i\le r_i\le N$。
• $1\le k_i\le 10^9$。