K‑th Smallest

Đề bài:

Cho một cây vô hướng có ~N~ đỉnh ~(1~ ~≤~ ~N~ ~≤~ ~10^5)~. Mỗi đỉnh ~i~ có một giá trị nguyên ~a[i]~ ~(0 ≤ a[i] ≤ 10^9)~.

Yêu cầu:

• Có ~Q~ truy vấn ~(1 ≤ Q ≤ 10^5)~. Mỗi truy vấn gồm ba số nguyên ~u~, ~v~, ~k~ ~(1 ≤ u, v ≤ N, 1 ≤ k ≤ length(path(u, v))).~
• Yêu cầu: trên đường đi duy nhất từ ~u~ tới ~v~, tìm giá trị thứ ~k~ khi các giá trị của các đỉnh trên đường đi được sắp xếp tăng dần.

Nếu ~k~ không hợp lệ ~(~ví dụ ~k~ lớn hơn độ dài đường đi~)~ thì in ~-1~.

Input:

N, Q
a[1] a[2] … a[N]
u1 v1 k1
u2 v2 k2
…
uQ vQ kQ

*Dòng 1: số đỉnh ~N~ và số truy vấn ~Q~. *Dòng 2: ~N~ số nguyên ~a~[i]. *Tiếp theo ~N‑1~ dòng: mỗi dòng chứa hai số ~x~, ~y~ ~(1~‑based~)~ mô tả một cạnh của cây. Cuối cùng ~Q~ dòng: mỗi dòng là một truy vấn ~u~, ~v~, ~k.~

Output:

Với mỗi truy vấn, in trên một dòng giá trị thứ k trên đường đi u → v. Nếu không tồn tại, in -1.

Ràng buộc:

~1 ≤ N, Q ≤ 10^5~ ~0 ≤ a[i] ≤ 10^9~ Tổng thời gian chạy ~≤ 1s~, bộ nhớ ~≤ 256~ MB.

Sample Input:

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

Sample Output:

3
5
2
8
2