Bessie 最近对魔法产生了兴趣，需要收集法力值来施展一个非常重要的咒语。Bessie 有 $N$ ($1\le N\le 18$) 个法力池，其中第 $i$ 个法力池每秒积累 $m_i$ 点法力值 ($1\le m_i\le 10^8$)。这些法力池由 $M$ ($0\le M\le N(N-1)$) 条有向边 $(a_i,b_i,t_i)$ 连接，意味着她可以在 $t_i$ 秒内从 $a_i$ 移动到 $b_i$ ($1\le a_i, b_i\le N$, $a_i\neq b_i$, $1\le t_i\le 10^9$)。每当 Bessie 到达一个法力池时，她可以收集该位置存储的所有法力值，并将其清空。在时间 $0$ 时，所有法力池均为空，Bessie 可以选择任意一个法力池作为起点。

回答 $Q$ ($1\le Q\le 2\cdot 10^5$) 个询问，每个询问由两个整数 $s$ 和 $e$ ($1\le s\le 10^9$, $1\le e\le N$) 指定。对于每个询问，确定如果 Bessie 必须在第 $s$ 秒结束时位于法力池 $e$，她最多能收集多少法力值。

输入格式

第一行包含 $N$ 和 $M$。

下一行包含 $m_1,m_2,\dots, m_N$。

接下来的 $M$ 行包含 $a_i,b_i,t_i$。输入中不会出现重复的有序对 $(a_i,b_i)$。

下一行包含 $Q$。

接下来的 $Q$ 行包含两个整数 $s$ 和 $e$。

输出格式

输出 $Q$ 行，每行对应一个询问的结果。

样例

样例输入 1

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

样例输出 1

5
50
100
1090

说明 1

第一个询问：Bessie 在 5 秒后从法力池 1 收集到 5 点法力值。

第二个询问：Bessie 在 5 秒后从法力池 2 收集到 50 点法力值。

第三个询问：Bessie 在 100 秒后从法力池 1 收集到 100 点法力值。

第四个询问：Bessie 在 90 秒后从法力池 1 收集到 90 点法力值，并在 100 秒后从法力池 2 收集到 1000 点法力值。

样例输入 2

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

样例输出 2

160000000
239999988050000000
119992550000000

说明 2

这是一个 Bessie 能够收集大量法力值的例子。

子任务

• 输入 3-4：$N\le 10, Q\le 100$
• 输入 5-9：$N\le 10$
• 输入 10-14：$Q\le 100$
• 输入 15-17：$N = 16$
• 输入 18-20：$N = 17$
• 输入 21-24：无额外限制。