Cho một cây với ~N~ nút, nút thứ i được gán một giá trị ~val[i]~. Cho ~Q~ truy vấn với mỗi truy vấn có dạng ~X~ ~K~. Với mỗi truy vấn, bạn phải tìm đường đi xuất phát từ nút ~X~ sao cho tổng các nút trên đường đi phải lớn hơn hoặc bằng ~K~ và số lượng nút trên đường đi phải đảm bảo là ít nhất. Nếu tồn tại đường đi thõa mãn yêu cầu thì in ra số lượng nút trên đường đi, ngược lại in ra -1.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~.

• Dòng thứ hai chứa ~N~ số nguyên cách nhau bởi khoảng trắng, số nguyên thứ i mô tả cho giá trị ~val[i]~.

• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~, ~v~ mô tả tồn tại đường đi giữa hai đỉnh ~~u và ~v~

• ~Q~ dòng tiếp theo, mỗi dòng chứa một truy vấn, tại dòng thứ i mô tả cho cặp Xi và ~K_i~.

Output

• Với mỗi truy vấn ~Q~ ghi ra trên một dòng là kết quả của truy vấn.

Ràng buộc

• ~1<=N<=10^5~

• ~1<=Q<=10~

• ~1<=val[i]<=10^9~

• ~1<=U,V,X<=N~

• ~1<=K<=10^{10}~

Ví dụ:

Input

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

Output

2
2