题目描述

一款游戏，游戏中有 $n$ 座小岛，第 $i$ 个岛有 $w_i$ 个金币，小岛间有 $m$ 座桥，每座桥连接两个小岛，没有任何一座桥两边的小岛编号相同，也没有任何两座桥连接的两个小岛编号分别相同。

玩家的任务是从编号为 $s$ 的岛走到编号为 $t$ 的岛。在一次任务中，每座桥玩家可以选定一个通行方向，只能从玩家选定的方向通过而不能从反方向通过，玩家在走的过程中可以采集最多k个经过的岛的金币，每次任务中每个金币最多采集一次，保证对于任意的 $s,t$ 满足 $s \neq t$，玩家都可以找到一种方法完成任务。

玩家会在游戏中完成 $q$ 个任务，每个任务是从编号为 $s$ 的小岛走到编号为 $t$ 的小岛，最多采集 $k$个小岛的金币。玩家想知道采集金币的最大值，你能告诉他吗？

输入格式

第一行一个整数，表示测试点编号。（样例中这个整数是0）

第二行一个整数 $n$，表示游戏中小岛个数。

第三行 $n$ 个整数 $w_i$ 表示游戏第 $i$ 个小岛的金币数。

接下来一行一个整数 $m$，表示游戏桥数。

接下来 $m$ 行，每行两个整数，第 $i$ 行表示内层游戏第 $i$ 座桥两边连接的小岛的编号。

接下来一行一个整数 $q$，表示外层游戏任务数量。

接下来 $q$ 行每行三个整数 $s,t,k$，表示这个任务的起点、终点和最多采集金币的次数。

输出格式

$q$ 行，每行一个整数，表示每次任务采集金币最大数量。

样例 #1

0
6
1 2 3 4 5 6
8
1 4
1 5
4 5
2 4
2 6
2 3
4 6
5 6
6
1 2 1
2 3 2
1 4 3
3 5 2
2 6 1
4 5 2

6
11
15
11
6
11

样例 #2

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

1
4
5
10
1

提示

样例说明

样例1中游戏地图如下

样例1第1个任务路线：$1\rightarrow4\rightarrow6$（采集）$\rightarrow2$

样例1第6个任务路线：$4\rightarrow6$（采集）$\rightarrow5$（采集）

数据规模和约定

$ 1 \leq n \leq 10^5,1\leq m\leq 3\cdot 10^5,1 \leq v_i,k \leq10^9 $ 。保证从一座小岛出发能够到达其它的所有小岛。

特殊性质A：$m=n-1$ 且第i座桥连接编号为 $i,i+1$ 的小岛。

特殊性质B：$m-n-1$。