Cho một cây (đồ thị vô hướng, liên thông, không có chu trình) gồm $N$ đỉnh. Các đỉnh được đánh số từ $1$ đến $N$, các cạnh được đánh số từ $1$ đến $N-1$. Mỗi đỉnh có một trọng số.

Viết chương trình thực hiện các truy vấn sau:

• u v k: In ra trọng số nhỏ thứ $k$ trong số các trọng số của các đỉnh trên đường đi từ $u$ đến $v$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100{,}000$).

Dòng thứ hai chứa trọng số của các đỉnh theo thứ tự từ đỉnh $1$ đến đỉnh $N$.

$N-1$ dòng tiếp theo, mỗi dòng chứa hai số $u$ và $v$ là hai đỉnh được nối bởi cạnh thứ $i$.

Dòng tiếp theo chứa số lượng truy vấn $M$ ($1 \le M \le 100{,}000$).

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Trọng số của các đỉnh luôn là số tự nhiên không lớn hơn $1{,}000{,}000$.

Dữ liệu ra

In ra kết quả của mỗi truy vấn theo thứ tự, mỗi kết quả trên một dòng.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

2
8
9
105
7