Bessie has recently taken an interest in magic and needs to collect mana for a very important spell. Bessie has $N (1≤N≤18)$ mana pools, the ith of which accumulates $m_i$ mana per second $(1≤m_i≤10^8)$. The pools are linked by a collection of $M (0≤M≤N(N−1))$ directed edges $(a_i,b_i,t_i)$, meaning that she can travel from $a_i$ to $b_i$ in $t_i$ seconds $(1≤a_i,b_i≤N, a_i \neq b_i, 1≤t_i≤10^9)$. Whenever Bessie is present at a pool, she can collect all the mana stored at that location, emptying it. At time $0$, all mana pools are empty, and Bessie can select any pool to start at.

Answer $Q (1≤Q≤2⋅10^5)$ queries, each specified by two integers $s$ and $e (1≤s≤10^9, 1≤e≤N)$. For each query, determine the maximum amount of mana Bessie can collect in $s$ seconds if she must be at mana pool $e$ at the end of the $s$th second.

First line contains $N$ and $M$.
Next line contains $m_1,m_2,…,m_N$.

Next $M$ lines contain $a_i,b_i,t_i$. No ordered pair $(a_i,b_i)$ appears more than once in the input.

Next line contains $Q$.

Next $Q$ lines contain two integers $s$ and $e$.

$Q$ lines, one for each query.

For sample input 1

First query: Bessie takes 5 mana from pool 1 after 5 seconds.

Second query: Bessie takes 50 mana from pool 2 after 5 seconds.

Third query: Bessie takes 100 mana from pool 1 after 100 seconds.

Fourth query: Bessie takes 90 mana from pool 1 after 90 seconds and 1000 mana from pool 2 after 100 seconds.

For sample input 2

An example where Bessie is able to collect much larger amounts of mana.