Problem M: 旅游3

Problem M: 旅游3

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 134  Solved: 30
[Submit] [Status] [Web Board] [Creator:]

Description

奥利奥旅游很多次了,以至于他做梦都在旅游。在他梦里的世界有N座城市它们环形排列,第i座城市到第i+1座城市得时间是的d[i],d[N]表示第N座城市到第一座城市的时间。城市之间的路是双向的。另外,城市之间还有传送门第i座传送门连接了u[i]和v[i]两座城市,时间花费是w[i]。现在他从任意一个城市出发,到任意一个城市旅游,请你求出花费的最短时间。

Input

第一行为2个整数N、M。
第二行为N个正整数d[i]。
接下来M行每行三个正整数u[i]、v[i]、w[i]。
第M+3行为一个正整数Q,表示需要计算的次数。
接下来Q行每行两个正整数x、y,奥利奥从城市x出发到城市y旅游。
1 ≤ N、Q ≤ 52000,1 ≤ M ≤ 20,1 ≤ u[i]、v[i]、x、y ≤ N,1 ≤ d[i]、w[i] ≤ 2^(30)

Output

Q行每行一个正整数表示该次旅行的最短时间。

Sample Input Copy

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

Sample Output Copy

1
5
2
2
3