Farmer John 想要公平地在两头奶牛 Bessie 和 Elsie 之间分配干草捆。他有 $N$ ($1\le N\le 2\cdot 10^5$) 个干草捆，按非递增顺序排列，其中第 $i$ 个干草捆有 $a_i$ 单位的干草 ($2\cdot 10^5\ge a_1\ge a_2 \ge \dots \ge a_N \ge 1$)。

Farmer John 正在考虑在 Bessie 和 Elsie 之间分配一个连续的干草捆区间 $a_l, \dots, a_r$。他决定按照从 $l$ 到 $r$ 的顺序处理这些干草捆，当处理第 $i$ 个干草捆时，他会将其分给当前拥有干草较少的那头奶牛（如果相等，则分给 Bessie）。

给定 $Q$ ($1\le Q\le 2\cdot 10^5$) 次询问，每次询问包含三个整数 $l, r, x$ ($1\le l\le r\le N$, $|x|\le 10^9$)。对于每次询问，如果 Bessie 开始时比 Elsie 多 $x$ 单位干草，请输出在处理完 $l$ 到 $r$ 的干草捆后，Bessie 比 Elsie 多出的干草单位数。注意，如果 Elsie 最终拥有的干草更多，该值为负数。

输入格式

第一行包含 $N$。

第二行包含 $a_1\dots a_N$。

第三行包含 $Q$。

接下来的 $Q$ 行包含 $l, r, x$。

输出格式

输出 $Q$ 行，包含每次询问的答案。

样例

输入 1

2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2

输出 1

1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1

说明 1

对于第 1 次询问，Elsie 开始时比 Bessie 多 $2$ 单位干草。处理完第 $1$ 个干草捆后，Bessie 获得 $3$ 单位干草，此时 Bessie 比 Elsie 多 $1$ 单位干草。

对于第 3 次询问，Elsie 和 Bessie 开始时拥有的干草数量相同。处理完第 $1$ 个干草捆后，Bessie 获得 $3$ 单位干草，此时 Bessie 比 Elsie 多 $3$ 单位干草。

对于第 9 次询问，Bessie 开始时比 Elsie 多 $1$ 单位干草，处理完第 $1$ 个干草捆后，Bessie 比 Elsie 少 $2$ 单位干草，处理完第 $2$ 个干草捆后，Bessie 比 Elsie 少 $1$ 单位干草。

输入 2

5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 2

输出 2

16
12
7
4
1
2
1

说明 2

在第 5 次询问中，有 $5$ 个干草捆需要处理。Bessie 获得 $4$ 单位，然后 Elsie 获得 $4$ 单位，然后 Bessie 获得 $3$ 单位，然后 Elsie 获得 $1$ 单位，最后 Elsie 获得 $1$ 单位。

子任务

• 输入 3: $Q\le 100$
• 输入 4-6: 至多 $100$ 个不同的 $a_i$
• 输入 7-22: 无额外限制。