$N$ 個の頂点からなる木（無向かつ閉路のない連結グラフ）がある。頂点には $1$ から $N$ までの番号が、辺には $1$ から $N-1$ までの番号が付けられている。各頂点には重みがある。

以下のクエリを実行するプログラムを作成せよ。

• u v k: $u$ から $v$ へのパス上に存在する頂点の重みのうち、$k$ 番目に小さい重みを出力する。

入力

最初の行に $N$ ($2 \le N \le 100{,}000$) が与えられる。

2 行目には、頂点 $1$ から順に各頂点の重みが与えられる。

3 行目から $N-1$ 行には、$i$ 番目の辺が接続する 2 つの頂点番号 $u$ と $v$ が与えられる。

次の行にはクエリの個数 $M$ ($1 \le M \le 100{,}000$) が与えられる。

次の $M$ 行には、クエリが 1 行に 1 つずつ与えられる。

頂点の重みは常に $1{,}000{,}000$ 以下の自然数である。

出力

各クエリの結果を順に 1 行に 1 つずつ出力する。

入出力例

入力 1

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

出力 1

2
8
9
105
7