Hành trình du lịch

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 (từ một thành phố bất kỳ có thể đi đến mọi thành phố khác). 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$ (tổng độ dài các con đường trên đường đi giữa $u$ và $v$). Nếu có nhiều thành phố thỏa mãn thì xe buýt sẽ di chuyển đến thành phố có chỉ số nhỏ nhất. 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; việc đi từ $u$ đến $v$ được tính là một tuyến đường.

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?

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $n,Q$ $(2\le n\le 2\times {10}^5,1\le 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 $xyw$ 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 $sk$: điểm xuất phát và số tuyến đường sẽ đi $(1\le s\le n,1\le k\le {10}^9)$.

Dữ liệu ra

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.

Ràng buộc

• $2\le n\le 2\times {10}^5$, $1\le Q\le 2\times {10}^5$.
• $|a_i|\le {10}^9$.
• $1\le x,y\le n$, $0<w\le {10}^9$; các con đường tạo thành một cây.
• $1\le s\le n$, $1\le k\le {10}^9$.

Subtasks

• Subtask 1 ($20\%$ số test, ứng với $20\%$ số điểm): $n,Q\le 200$, $k\le 200$.
• Subtask 2 ($25\%$ số test khác, ứng với $25\%$ số điểm): $n,Q\le 2000$.
• Subtask 3 ($25\%$ số test khác, ứng với $25\%$ số điểm): $k=1$.
• Subtask 4 ($30\%$ số test còn lại, ứng với $30\%$ số điểm): không có ràng buộc gì thêm.

Bài được chấm theo từng test, mỗi test có cùng số điểm.

Ví dụ