Description

There is a dungeon with $N + 1$ floors. There are $M$ players in the dungeon. The floors are numbered from $1$ to $N + 1$, starting from the entrance. The players are numbered from $1$ to $M$.

A player uses energy to move from a floor to the next floor. The amount of energy a player uses is $A_i$ if he moves from the floor $i$ ($1 \leq i \leq N$) to the floor $i + 1$. As this is a one-way dungeon, the only possible moves between floors are from the floor $i$ to the floor $i + 1$ for some $i$ ($1 \leq i \leq N$).

In each of the floors from the floor $1$ to the floor $N$, inclusive, there is a fountain of recovery. At the fountain of recovery in the floor $i$ ($1 \leq i \leq N$), a player can increase his energy by $1$ paying $B_i$ coins. A player can use a fountain multiple times as long as he has needed coins. However, each player has a maximum value of his energy, and his energy cannot exceed that value even if he uses a fountain of recovery.

Now the player $j$ ($1 \leq j \leq M$) is in the floor $S_j$. His current energy is 0. His maximum value of energy is $U_j$. He wants to move to the floor $T_j$. His energy cannot be smaller than $0$ along the way. How many coins does he need?

Write a program which, given the information of the dungeon and the players, determines whether it is possible for each player to move to the destination so that his energy does not become smaller than $0$ along the way. If it is possible to move, the program should calculate the minimum number of coins he needs.

Input

Read the following data from the standard input. Given values are all integers.

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

Output

Write $M$ lines to the standard output. The $j$-th line ($1 \leq j \leq M$) should contain the minimum number of coins the player $j$ needs to move to the floor $T_j$. If it is impossible for the player $j$ to move to the floor $T_j$, output −1 instead.

Sample 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
29
3
22

Since the maximum value of energy of the player $1$ is $3$, the player $1$ cannot move from the floor $2$ to the floor $3$. Hence the first line of output is −1.

On the other hand, the maximum value of energy of the player $2$ is $4$. The player $2$ can move to the floor $6$ by the following way.

• In the floor $1$, he pays $8$ coins, and his energy becomes $4$. Then he moves to the floor $2$, and his energy becomes $1$.
• In the floor $2$, he pays $15$ coins, and his energy becomes $4$. Then he moves to the floor $3$, and his energy becomes $0$.
• In the floor $3$, he pays $4$ coins, and his energy becomes $4$. Then he moves to the floor $4$, and his energy becomes $3$.
• In the floor $4$, he does not pay coins. Then he moves to the floor $5$, and his energy becomes $2$.
• In the floor $5$, he pays $2$ coins, and his energy becomes $4$. Then he moves to the floor $6$, and his energy becomes $0$.

In total, the player $2$ pays $29$ coins. Since it is impossible for the player $2$ to move to the floor $6$ by paying less than $29$ coins, the second line of output is $29$.

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

208
112
179
248
158
116
234
162
42
-1

This sample input satisfies the constraints of the subtask $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

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

Constraints

• $1 \leq N \leq 2 \times 10^5$.
• $1 \leq M \leq 2 \times 10^5$.
• $1 \leq A_i \leq 2 \times 10^5$ ($1 \leq i \leq N$).
• $1 \leq B_i \leq 2 \times 10^5$ ($1 \leq i \leq N$).
• $1 \leq S_i < T_i \leq N+1$ ($1 \leq j \leq M$).
• $1 \leq U_i \leq 10^8$ ($1 \leq j \leq M$).

Subtasks

1. ($11$ points) $N \leq 3000$, $M \leq 3000$.
2. ($14$ points) $U_1 = U_2 = \ldots = U_M$.
3. ($31$ points) $T_j = N + 1$ ($1 \leq j \leq M$).
4. ($44$ points) No additional constraints.