To watch the sunrise, Little R came to the east coast of Country C.

Along the coastline of the east coast, there are $n$ cities arranged from north to south, numbered $1$ to $n$. Cities with smaller numbers are located to the north of cities with larger numbers. Adjacent cities are connected by a coastal highway, where the length of the road connecting city $i$ and $i+1$ is $l_i$ kilometers.

Little R has a car that consumes one unit of gasoline for every kilometer traveled. There are no gas stations on the roads between cities, so Little R can only choose to refuel in the cities along the way. The price of gasoline per unit in city $i$ is $p_i$. If Little R's car runs out of gasoline, it will immediately stall and be unable to proceed. The car's fuel tank has a maximum capacity of $V$ units.

Little R has planned $m$ trips to watch the sunrise. In the $i$-th trip, Little R stays in city $s_i$ at night and needs to drive to city $t_i$ the next morning. For certain reasons, Little R always travels from a city with a smaller number to a city with a larger number, i.e., $s_i < t_i$. Because time is tight, Little R always chooses the shortest route for each trip. Based on choosing the shortest route, Little R wants to arrange refueling locations optimally to minimize the cost of each trip. At the beginning of the $i$-th trip, the car's fuel tank contains $v_i$ units of gasoline ($0 \le v_i \le V$).

Note that each trip is independent; the fuel amount $v_i$ at the start of the $i$-th trip is always $v_i$ and is not affected by the remaining fuel at the end of the previous trip.

Input

The first line contains three space-separated positive integers $n, m, V$, representing the number of cities, the number of trips, and the fuel tank capacity, respectively.

The second line contains $n$ space-separated positive integers, where the $i$-th integer represents $p_i$.

The third line contains $n-1$ space-separated positive integers, where the $i$-th integer represents $l_i$.

The next $m$ lines each contain three space-separated integers $s_i, t_i, v_i$, representing that in the $i$-th trip, Little R starts from $s_i$ to $t_i$ with $v_i$ units of gasoline in the tank.

Output

Output $m$ lines, where the $i$-th line represents the minimum cost for the $i$-th trip.

Examples

Input 1

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

Output 1

32
38
26
14
0

Input 2

10 10 10
3 6 6 5 1 1 9 4 1 6
3 1 2 1 3 7 7 1 3
4 8 5
2 7 6
2 9 5
1 5 3
4 7 8
3 4 6
1 3 3
1 2 6
3 7 1
2 5 1

Output 2

45
8
52
12
3
0
3
0
21
17

Subtasks

For 100% of the data, $n \le 10^6$, $m \le 10^6$, $1 \le V \le 10^{18}$, $1 \le s_i < t_i \le n$, $0 \le v_i \le V$, $1 \le l_i \le \min(V, 10^6)$, $1 \le p_i \le 5 \times 10^6$.

There are 20 test cases in total, each worth 5 points. The constraints for each test case are as follows:

Hack data on QOJ is not subject to the equality constraints in the table.

After submitting your code, the pretest data will be evaluated and the results returned. The pretest data for this problem contains 7 test cases, where the $i$-th test case satisfies the data scale constraints of the $(i+1)$-th row in the table.

Note: The evaluation results of the pretest data have no relation to the final evaluation results.