ami có một cây \(n\) nút, mỗi đỉnh được đánh số từ \(1\) đến \(n\), nút \(i\) được gắn số \(a_i\). Một đường đi từ \(u\) đến \(v\) là đường đi xuất phát từ \(u\), đi qua các đỉnh kề không quá một lần và kết thúc ở \(v\). Các bạn cần tính xem có bao nhiêu giá trị \(D \geq 0\) mà tồn tại ít nhất một đường đi giữa 2 nút trên cây là một cấp số cộng công sai \(D\). Với mỗi \(D\) tìm được, hãy tìm ra đường đi có độ dài lớn nhất thoả mãn điều kiện. Độ dài đường đi giữa 2 nút \(u\) và \(v\) là số lượng nút nằm trên đường đi đó.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) là số đỉnh của cây.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa 2 số \(u\) và \(v\) biểu diễn một cạnh nối giữa 2 đỉnh \(u\) và \(v\).
• Dòng tiếp theo gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\). \(a_i\) là giá trị trên nút \(i\).

Output

• Gồm một vài dòng, mỗi dòng có 2 số \(D\) và \(x\). Với ý nghĩa, đường đi dài nhất có công sai \(D\) có độ dài là \(x\).
• Các bạn cần in \(D\) theo thứ tự tăng dần.

Example

9
1 2
1 3
2 4
2 5
3 6
3 7
5 8
7 9
1 4 0 3 7 -1 -1 10 -2

1 4
3 4

Giới hạn

• \(2 \leq n \leq 3 \cdot 10^5\)
• \(1 \leq a_i \leq 10^9\)