Karl is an impatient guy. He always wants to find the fastest way to solve any problem. As a delivery man, it's a very good personality because he can make the work more efficient.
Now, Karl gets T tasks from his boss, which requires him to send the goods from cities to cities. There are N cities , numbered from 1 to N. And N-1 directional roads connect these cities. The ith road connects City i to City i+1 with a length Di. Moreover, there are M small Paths connect cities. They are also directional, and each of them has a length Qi. People can go through both roads and paths.
Karl wants to find the shortest way to complete every task. But he is afraid to walk on the small path. So, in every task, he can only pass through at most 1 small path. He gets a little faint about this question, so he asked for your help.
Input
There are few test cases. NOTICE that's no empty line between each test case. For each test case:
The first line contains two integers N , M(1 <= N <= 100000 , 1 <= M <= 200000), indicating there are N cities and M small paths.
The second line contains N-1 integers, indicating the length Di(1 <= Di <= 100000) of the ith directional road, which connects City i to City i+1.
The following M lines indicates M small paths. Each line contains 3 integers Ai , Bi , Qi, (1 <= Ai <= N , 1 <= Bi <= N , 1 <= Qi <= 100000)indicating this directional small path connects City Ai to City Bi with length Qi.
The next line contains a integer T(1 <= 200000), which means there are T tasks.
The following T lines indicates the T tasks. Each line contains 2 integers Ui(1 <= Ui <= N) , Vi(1 <= Vi <= N), indicating you are asked to find the shortest way from City Ui to City Vi with the requirements.
We promise that there is an answer to each Task.(There should be at least one way from City Ui to City Vi with requirements)
Output
For each test case, for every task, output a integer in a line which shows the shortest way for the query with requirements.
We promise that each answer will not exceed 2^31 - 1.
Sample Input
5 3
1 2 3 4
2 4 2
1 3 2
5 1 3
5
1 4
4 2
3 1
1 3
1 5
Sample Output
3
8
10
2
7
