Mana Collection

문제

Bessie has recently taken an interest in magic and needs to collect mana for a very important spell. Bessie has $NN$ ($1\le N\le 181\backslash le\; N\backslash le\; 18$) mana pools, the $ii$th of which accumulates $m_{i}m\_i$ mana per second ($1\le m_i\le {10}^{8}1\backslash le\; m\_i\backslash le\; 10^8$). The pools are linked by a collection of $MM$ ($0\le M\le N(N-1)0\backslash le\; M\backslash le\; N(N-1)$) directed edges $(a_i,b_i,t_i)(a\_i,b\_i,t\_i)$, meaning that she can travel from $a_{i}a\_i$ to $b_{i}b\_i$ in $t_{i}t\_i$ seconds ($1\le a_i,b_i\le N1\backslash le\; a\_i,\; b\_i\backslash le\; N$, $a_i\mathrm{\ne }{b}_{i}a\_i\backslash neq\; b\_i$, $1\le t_i\le {10}^{9}1\backslash le\; t\_i\backslash le\; 10^9$). Whenever Bessie is present at a pool, she can collect all the mana stored at that location, emptying it. At time $00$, all mana pools are empty, and Bessie can select any pool to start at.

Answer $QQ$ ($1\le Q\le 2\cdot {10}^{5}1\backslash le\; Q\backslash le\; 2\backslash cdot\; 10^5$) queries, each specified by two integers $ss$ and $ee$ ($1\le s\le {10}^{9}1\backslash le\; s\backslash le\; 10^9$, $1\le e\le N1\backslash le\; e\backslash le\; N$). For each query, determine the maximum amount of mana Bessie can collect in $ss$ seconds if she must be at mana pool $ee$ at the end of the $ss$th second.

입력

First line contains $NN$ and $MM$.

Next line contains $m_1,m_2,\dots ,m_{N}m\_1,m\_2,\backslash dots,\; m\_N$.

Next $MM$ lines contain $a_i,b_i,t_{i}a\_i,b\_i,t\_i$. No ordered pair $(a_i,b_i)(a\_i,b\_i)$ appears more than once in the input.

Next line contains $QQ$.

Next $QQ$ lines contain two integers $ss$ and $ee$.

출력

$QQ$ lines, one for each query.

2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2

5
50
100
1090

4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4

160000000
239999988050000000
119992550000000