問題文

頂点数 n の木があり，頂点 i (i = 1, ..., n) には正の整数 a_i が書かれている． q個の質問に答えよ.

各質問は3つの整数からなり， j 番目の質問は x_j, v_j, w_j で与えられる．
木の頂点 v_j から w_j への最短のパスの頂点に書かれている数 a_i で， x_j を順番に割った余りを出力せよ． 言い換えると，v_j から w_j への最短パスが p_1, ..., p_k (頂点数 k , p_1 = v_j, p_k = w_j ) であるとき， ((...((x_j % a_{p_1}) % a_{p_2}) ...) % a_{p_{k-1}} ) % a_{p_k} を出力せよ．

ただし x % y は x を y で割った余りを取る演算とする．

n q
a_1 ... a_n
b_1 c_1
:
b_{n-1} c_{n-1}
x_1 v_1  w_1
:
x_q v_q  w_q

入力例1

5 2
8 6 4 3 2
1 2
2 3
3 4
4 5
15 1 5
15 2 5

出力例1

1
0

入力例2

8 5
18 29 52 64 4 59 89 15
1 2
1 3
1 4
2 5
3 6
3 7
4 8
99 6 7
102 5 8
15 2 6
84 7 8
19 1 1

出力例2

40
2
15
14
1