Sau chuỗi ngày ôn và thi mệt mỏi, Bờm quyết định du lịch đến đất nước Byteland. Đất nước xinh đẹp này có ~n~ thành phố, các thành phố kết nối với nhau bởi ~n-1~ con đường hai chiều. Con đường thứ ~i~ nối từ thành phố ~x~ đến thành phố ~y~ có độ dài ~w~. Thêm nữa, qua quá trình khảo sát Bờm có lên thang điểm về độ đẹp cho mỗi thành phố. Độ đẹp của thành phố thứ ~i~ được đánh giá là ~a_i~.

Việc đi lại giữa các thành phố được thực hiện bằng xe buýt. Cách vận hành xe buýt ở đây cũng rất đặc biệt: Giả sử xe buýt đang ở thành phố ~u~, nó sẽ xác định tuyến đi tiếp theo bằng cách chọn một thành phố ~v~ (khác ~u~) có ~a_v - d(u,v)~ là lớn nhất. Trong đó ~d(u,v)~ được định nghĩa là khoảng cách đi từ ~u~ đến ~v~ (nếu có nhiều thành phố thỏa mãn thì nó sẽ di chuyển đến thành phố có chỉ số nhỏ nhất). Và khi đã chọn được điểm đến là thành phố ~v~ thì xe buýt sẽ đi thẳng từ ~u~ đến ~v~ mà không dừng ở các thành phố trung gian.

Yêu cầu: Cho ~Q~ truy vấn, mỗi truy vấn có hai tham số ~s, k~ ứng với việc Bờm xuất phát từ thành phố ~s~ và di chuyển qua ~k~ tuyến đường bằng xe buýt theo cách mô tả ở trên. Hãy cho biết, với mỗi truy vấn thì Bờm sẽ kết thúc chuyến đi ở thành phố nào?

Input

• Dòng đầu chứa hai số nguyên dương ~n, Q~ ~(n, Q \le 2 \times 10^5)~ là số thành phố và số truy vấn.
• Dòng hai chứa ~n~ số nguyên ~a_1, a_2, \dots a_n~ là vẻ đẹp của ~n~ thành phố ~(|a_i| \le 10^9)~.
• ~n-1~ dòng tiếp theo dạng ~x \ y \ w~ mô tả ~n-1~ con đường ~(1 \le x, y \le n, 0 < w \le 10^9)~.
• ~Q~ dòng tiếp là truy vấn dạng ~s \ k~: điểm xuất phát và số tuyến đường sẽ đi.

Output

Gồm ~Q~ dòng, mỗi dòng in ra chỉ số thành phố Bờm sẽ kết thúc ở mỗi truy vấn.

Scoring

Sample Input 1

5 4
1 2 3 4 5
1 4 3
3 2 5
4 3 2
1 5 2
1 1
2 3
3 2
5 1

Sample Output 1

5
3
3
1

Notes

Hành trình của tour của Bờm:

~1 \rightarrow 5~

~2 \rightarrow 3 \rightarrow 4 \rightarrow 5~

~3 \rightarrow 4 \rightarrow 5~

~5 \rightarrow 1~