有一个拥有 $N + 1$ 层楼的地下城。地下城中有 $M$ 名玩家。楼层编号从 $1$ 到 $N + 1$，从入口开始。玩家编号从 $1$ 到 $M$。

玩家消耗能量从一层移动到下一层。如果玩家从 $i$ 层 ($1 \le i \le N$) 移动到 $i + 1$ 层，消耗的能量为 $A_i$。由于这是一个单向地下城，楼层之间唯一的移动方式是从 $i$ 层移动到 $i + 1$ 层 ($1 \le i \le N$)。

在从 $1$ 到 $N$ 的每一层中，都有一个恢复喷泉。在 $i$ 层 ($1 \le i \le N$) 的恢复喷泉处，玩家可以支付 $B_i$ 枚硬币来增加 $1$ 点能量。只要玩家有足够的硬币，就可以多次使用喷泉。然而，每位玩家都有一个能量上限，即使使用恢复喷泉，其能量也不能超过该值。

现在，玩家 $j$ ($1 \le j \le M$) 位于 $S_j$ 层。他当前的能量为 $0$。他的能量上限为 $U_j$。他想要移动到 $T_j$ 层。在移动过程中，他的能量不能小于 $0$。他需要多少枚硬币？

编写一个程序，给定地下城和玩家的信息，确定每位玩家是否能够移动到目的地，使得在移动过程中能量始终不小于 $0$。如果可以移动，程序应计算他所需的最少硬币数量。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$N \ M$ $A_1 \ \dots \ A_N$ $B_1 \ \dots \ B_N$ $S_1 \ T_1 \ U_1$ $\vdots$ $S_M \ T_M \ U_M$

输出格式

向标准输出写入 $M$ 行。第 $j$ 行 ($1 \le j \le M$) 应包含玩家 $j$ 移动到 $T_j$ 层所需的最少硬币数量。如果玩家 $j$ 不可能移动到 $T_j$ 层，则输出 $-1$。

数据范围

• $1 \le N \le 200\,000$
• $1 \le M \le 200\,000$
• $1 \le A_i \le 200\,000$ ($1 \le i \le N$)
• $1 \le B_i \le 200\,000$ ($1 \le i \le N$)
• $1 \le S_j < T_j \le N + 1$ ($1 \le j \le M$)
• $1 \le U_j \le 100\,000\,000$ ($1 \le j \le M$)

子任务

1. (11 分) $N \le 3\,000, M \le 3\,000$
2. (14 分) $U_1 = U_2 = \dots = U_M$
3. (31 分) $T_j = N + 1$ ($1 \le j \le M$)
4. (44 分) 无附加限制

样例

样例输入 1

5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9

样例输出 1

-1
29
3
22

样例输入 2

10 10
1 8 9 8 1 5 7 10 6 6
10 10 2 8 10 3 9 8 3 7
2 11 28
5 11 28
7 11 28
1 11 18
3 11 18
8 11 18
4 11 11
6 11 11
10 11 11
9 11 5

样例输出 2

208
112
179
248
158
116
234
162
42
-1

说明

样例 2 满足子任务 3 的限制。

样例输入 3

20 20
2 3 2 11 4 6 9 15 17 14 8 17 3 12 20 4 19 8 4 5
19 3 18 2 13 7 5 19 10 1 12 8 1 15 20 1 13 2 18 6
12 15 67
7 15 18
16 17 14
9 21 97
1 19 43
3 18 31
16 20 70
7 20 28
1 16 61
3 5 69
9 10 15
2 13 134
11 19 23
16 20 14
5 21 16
15 20 11
7 11 54
7 16 16
13 17 10
3 15 135

样例输出 3

151
591
4
284
339
517
35
581
254
58
-1
178
519
-1
-1
-1
219
-1
-1
214