Note: Đề này tạo khá lâu rồi
Sau khi vượt qua gần như toàn bộ thử thách của cuộc hành trình, ledinhbaonam được dẫn tới khu vực sâu nhất của LQDOJ — nơi cất giữ thử thách cuối cùng dành cho những người muốn chạm tới đỉnh cao.
Tại đây tồn tại một mạng lưới cổ đại gồm \(n\) điểm năng lượng, được nối với nhau bởi \(n-1\) liên kết hai chiều sao cho từ bất kỳ điểm nào cũng có thể đi tới mọi điểm khác, và giữa hai điểm bất kỳ luôn tồn tại đúng một đường đi đơn.
Mỗi điểm năng lượng thứ \(i\) mang giá trị sức mạnh \(a_i\).
Theo ghi chép mà PhuocThien để lại, sức mạnh thật sự của mạng lưới không nằm ở từng điểm riêng lẻ, mà nằm trong những đoạn liên tiếp trên các đường đi.
Tuy nhiên, Protoype đã đặt lên toàn bộ hệ thống một quy tắc đặc biệt:

• Chỉ những đoạn có số lượng đỉnh chia hết cho \(k\) mới có thể được kích hoạt.
  uia đưa ra \(q\) truy vấn.
  Mỗi truy vấn gồm hai đỉnh \(u, v\), yêu cầu bạn xác định:
• Trên đường đi đơn từ \(u\) đến \(v\), hãy chọn một đoạn liên tiếp gồm số đỉnh chia hết cho \(k\) sao cho tổng giá trị các đỉnh trong đoạn là lớn nhất.
  Nếu không tồn tại đoạn hợp lệ, in ra INF.

Input

• Dòng đầu chứa ba số nguyên \(n, q, k\) (\(1 \le n, q \le 2 \cdot 10^5, 1 \le k \le 20\))
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\))
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) (\(1 \le x, y \le n,\ x \ne y\)) mô tả một cạnh của cây
• \(q\) dòng cuối, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\))

Output

Với mỗi truy vấn, in ra một số nguyên là giá trị lớn nhất của đoạn hợp lệ trên đường đi từ \(u\) đến \(v\).
Nếu không tồn tại đoạn thỏa mãn, in ra INF.

Example

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

8
11
4