Nobita đang ngồi làm bài tập ở nhà, nhưng được một lát cậu ta lại chán chỉ muốn đi ngủ. Doraemon thấy vậy liền nảy ra một ý tưởng để giúp Nobita phấn chấn hơn - đó là đưa Nobita đến vùng đất táo đỏ thần kỳ về hạnh phúc. Nghe xong, Nobita liền bật dậy và cùng Doraemon bước vào cánh cửa thần kỳ để đến với vùng đất táo đỏ kia. Khi đến nơi, Nobita choáng ngợp với một cánh đồng mênh mông chỉ toàn táo màu đỏ. Doraemon dẫn Nobita đến trước một cây táo khổng lồ và nói với Nobita rằng đây là cây táo tình yêu; nếu ăn được một cặp táo hợp nhau trên cây thì tình cảm giữa hai người ăn táo sẽ trở nên khăng khít hơn. Nghe đến đây Nobita liền sáng mắt lên và hỏi Doraemon làm sao để hái được cặp táo hợp nhau đó, vì cậu rất muốn đem cặp táo đó tặng ngay cho Shizuka.

Để dễ tưởng tượng, cây táo được biểu diễn dưới dạng một đồ thị dạng cây với mỗi đỉnh đại diện cho một quả táo, cây gồm \(n\) đỉnh được đánh số từ \(1, 2, 3, \dots, n\) và \(n - 1\) cạnh. Mỗi quả của cây đều có một chỉ số hạnh phúc, tương ứng \(a_1, a_2, a_3, \dots, a_n\) lần lượt là chỉ số hạnh phúc của các đỉnh từ \(1\) đến \(n\).

Ta định nghĩa một số \(X\) được gọi là số siêu hạnh phúc bậc \(k\) nếu số đó có căn bậc \(k\) là một số tự nhiên (hay nói cách khác: số đó có thể biểu diễn dưới dạng \(y^k\) với \(y\) là một số tự nhiên).

Ví dụ:

• \(k = 2\): Các số siêu hạnh phúc có thể là \(4\) (vì \(2^2 = 4\)), \(81\) (vì \(9^2 = 81\)).
• \(k = 3\): Các số siêu hạnh phúc có thể là \(8\) (vì \(2^3 = 8\)), \(8000\) (vì \(20^3 = 8000\)).

Ta gọi một cặp quả táo là hợp nhau nếu tích của \(2\) chỉ số hạnh phúc của \(2\) quả táo đó là số siêu hạnh phúc bậc \(k\).

Nobita quyết định sử dụng tài năng bắn súng của mình, nhưng cậu chỉ có khả năng bắn rơi tất cả các trái táo nằm trên một đường đi đơn bất kì trên cây. Cậu có \(q\) câu hỏi như sau:

Nobita lo lắng nên cậu ấy nhờ các bạn giải đáp các câu hỏi để có thể chọn ra được cặp táo phù hợp nhất dành tặng cho Shizuka.

Input

• Dòng đầu chứa ba số nguyên: \(n, k, q\) (\(1 \le n, q \le 10^5\), \(1 \le k \le 5\)).
• Dòng tiếp theo là dãy số nguyên dương \(a_1, a_2, a_3, \dots, a_n\) (\(1 \le a_i \le 10^6\)).
• \(n - 1\) dòng tiếp theo lần lượt là các cạnh của đồ thị (đảm bảo đồ thị đã cho là đồ thị dạng cây).
• Tiếp theo là \(q\) dòng chứa các câu hỏi của Nobita, mỗi câu hỏi có dạng \((u, v)\) với \(1 \le u, v \le n\).

Output

• Ghi ra \(q\) dòng, mỗi dòng tương ứng với kết quả của một câu hỏi.

Example

6 3 4
1 15 30 7 49 10
1 4
4 2
4 3
4 5
6 5
4 5
1 6
2 4
1 1

1
1
0
0

Scoring

• Subtask \(1\) (\(10\%\) số test): \(1 \le n \le 100\), \(k = 2\), \(1 \le q \le 100\).
• Subtask \(2\) (\(20\%\) số test): \(1 \le n \le 1000\), \(1 \le q \le 1000\).
• Subtask \(3\) (\(20\%\) số test): Mỗi đỉnh thuộc đồ thị có bậc tối đa là \(2\).
• Subtask \(4\) (\(50\%\) số test): Không có ràng buộc gì thêm.