問題

グラフが与えられる．

• N 個の頂点があり，頂点に 1 から N の番号が付いている．
• これらの頂点は，N - 1 本の辺によりツリー状に接続されている．
• 各頂点 v には数字 a_v が定まっている．

下図は，与えられるグラフの例である． 各頂点には上部に頂点の番号が，下部にその頂点に定められた数字 (a_v) が書かれている．

与えられるグラフの例

次に，Q 個の以下のようなクエリが与えられる．

• 各クエリ q には，頂点 v_q, w_q と整数 l_q が指定される．
• 頂点 v_q から頂点 w_q への経路に含まれる頂点の数字のうち l_q 番目に小さいものを求めよ．
  • 経路は単純なもののみを考える．単純な経路とは，同じ頂点を二度通らない経路のことである．グラフがツリー状であることから，単純な経路は一意である．
  • 経路には両端点（すなわち頂点 v_q, w_q）を含むものとする．

例えば，上図のグラフが与えられている時， (v_q, w_q, l_q) = (1, 6, 3) なるクエリ q に対する答えは 7 である． これは，頂点 1 から頂点 6 への経路には頂点 1, 3, 4, 6 が含まれており， それらに定まった数字 2, 5, 8, 7 の 3 番目めに小さな数字は 7 であることによる．

グラフとクエリを受け取り，結果を出力するプログラムを作成せよ．

入力

入力の最初の行は 2 つの整数 N, Q を含む． これは，頂点数とクエリの数を表す．

続く N 行は，各頂点の持つ数字を表す． これらの行のうちの v 行目は 1 つの整数 x_v が書かれており， これは頂点 v の持つ数字を表す．

続く N - 1 行は，辺の情報を表す． これらの行のうちの e 行目は 2 つの整数 a_e, b_e が書かれており， これらは辺 e が結ぶ 2 つの頂点を表す．

続く Q 行は，クエリの情報を表す． これらの行のうちの q 行目は 3 つの整数 v_q, w_q, l_q が書かれており， これらはクエリ q の情報を表す．

出力

出力は Q 行からなる．q 行目にクエリ q の答えを出力せよ．

入力に関する制約

• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ x_v ≤ 10⁹
• 1 ≤ a_e, b_e ≤ N
• 1 ≤ v_q, w_q ≤ N
• 頂点 v_q から頂点 w_q への経路には l_q 個以上の頂点が存在する．

入出力例

入力例:

6 11
2
4
5
8
9
7
1 3
2 3
3 4
4 5
4 6
1 6 1
1 6 2
1 6 3
1 6 4
1 2 1
1 2 2
1 2 3
2 5 1
2 5 2
2 5 3
2 5 4

入力例に対する出力:

2
5
7
8
2
4
5
4
5
8
9