Thứ Hạng Trên Đường Cây

Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Đỉnh $i$ mang trọng số $w_i$. Mỗi truy vấn yêu cầu xét tất cả trọng số của các đỉnh nằm trên một đường đơn của cây và tìm phần tử nhỏ thứ $k$ trong đa tập đó; vì vậy hai đỉnh có cùng trọng số vẫn được tính thành hai phần tử riêng.

Các truy vấn được mã hóa trực tuyến. Gọi $last$ là đáp án của truy vấn ngay trước, với $last=0$ trước truy vấn đầu tiên. Một dòng truy vấn ghi $U$ $v$ $k$, nhưng đầu mút thứ nhất thật sự là

Đầu mút $v$ và số thứ hạng $k$ không bị mã hóa. Sau khi in đáp án hiện tại, hãy gán đáp án đó cho $last$ trước khi đọc nghĩa của truy vấn kế tiếp.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $w_1,w_2,\dots ,w_n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai đỉnh nối bởi một cạnh.
• $m$ dòng cuối, mỗi dòng chứa ba số nguyên $U,v,k$.
• Dữ liệu bảo đảm sau khi giải mã, $u$ và $v$ là các đỉnh hợp lệ, còn $k$ không vượt quá số đỉnh trên đường từ $u$ đến $v$.

Output

• Với mỗi truy vấn, in trọng số nhỏ thứ $k$ trên đường tương ứng, mỗi đáp án trên một dòng.

Constraints

• $1\le n,m\le 10^5$.
• $1\le w_i\le 2^{31}-1$.
• $0\le U\le 2^{31}-1,1\le v\le n$.
• Sau giải mã: $1\le U\mathrm{xor}last\le n$.
• $1\le k\le \text{soˆˊ đỉnh treˆn đường được hỏi}$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6 4
8 3 10 3 6 12
1 2
1 3
2 4
2 5
3 6
4 6 3
13 4 2
2 5 2
0 6 1

8
3
6
12