Lưu ý : Bài này chỉ khác phiên bản dễ ở cấu trúc của dữ liệu, và giới hạn của giá trị a_i

Ami có một cái cây (đơn đồ thị vô hướng liên thông không chu trình) có n nút. Các nút được đánh số từ 1. Trên các nút của cây có các giá trị, giá trị trên nút i là v_i. Đường đi từ nút u đến v là một dãy a₁, a₂, a₃, ..., a_t thoả mãn các điều kiện sau :

     1) a₁ = u và a_t = v

     2) Đường đi là ngắn nhất giữa 2 đỉnh u và v

     3) Với mọi i < t, có cạnh nối trực tiếp giữa a_i và a_i+1.

Các bạn cần tính xem có bao nhiêu giá trị D ≥ 0 mà tồn tại ít nhất một đường đi giữa 2 nút u và v bất kỳ trên cây là một cấp số cộng với công sai D. Với mỗi D ≥ 0 tìm được, hãy tìm xem đường đi dài nhất thoả mãn điều kiện đó.

Input

Dòng đầu tiên gồm một số nguyên dương n (n ≤ 3*10⁵) 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 (u , v ≤ n), 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₁, a₂, a₃, ..., a_n (|a_i| ≤ 10⁹). 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 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.