Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tính tổng của ~|a_i-a_j|~ với mọi cặp ~(i,j)~ thỏa mãn ~1 \le i < j \le n~.

Input

• Dòng đầu gồm ~1~ số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra kết quả tìm được.

Sample Test

Input

3
5 1 2

Output

8

Cho số ~n~ và dãy số nguyên ~a~ gồm ~n~ phần tử, hãy tìm đoạn con liên tiếp dài nhất của dãy ~a~ có trung bình cộng lớn hơn hoặc bằng ~k~ cho trước.

Input

• Dòng đầu gồm 2 số nguyên ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(|k| \le 10^6)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra một số nguyên là độ dài của dãy con liên tiếp dài nhất thỏa mãn.

Sample Test

Input

7 3
1 5 2 3 1 4 1

Output

5

Cho mảng ~a~ có ~n~ phần tử nguyên dương, có thể thực hiện thao tác sau vô số lần hoặc không lần nào: Chọn 2 phần tử khác nhau bất kì trong mảng, gán lại giá trị cho phần tử lớn hơn bằng giá trị tuyệt đối hiệu 2 phần tử. Hỏi tổng nhỏ nhất có thể của mảng ~a~ sau khi thực hiện các thao tác trên là bao nhiêu?

Input

• Dòng đầu tiên gồm số nguyên dương ~1 \le n \le 10^5~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le a_i \le 10^9~ là các phần tử của mảng ~a~.

Output

• In ra tổng nhỏ nhất có thể.

Sample Test

Input:

2
1 2

Output:

2

Nitori mở thương hiệu dưa chuột mới, có ~n~ chi nhánh được kết nối với nhau theo dạng cây. Có tất cả ~C~ loại dưa chuột, cửa hàng thứ ~i~ bán loại dưa chuột ~a_i~. Ngày hôm nay có ~q~ khách hàng ghé thăm các cửa hàng của cô, mỗi khách hàng thứ ~i~ ghé thăm cửa hàng ~x_i~ và đặt loại dưa chuột ~y_i~, có thể cửa hàng ~x_i~ không bán loại dưa chuột ~y_i~ nên cô cần tới cửa hàng gần nhất lấy.

Hỏi với mỗi khách hàng, thời gian tối thiểu cần để phục vụ là bao nhiêu?

Input

• Dòng đầu tiên là số nguyên dương ~1 \le n \le 10000~.
• ~n - 1~ dòng tiếp theo là đường đi trực tiếp giữa 2 cửa hàng trong hệ thống.
• Dòng tiếp theo là số nguyên dương ~C \le n~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le a_i \le C~.
• Dòng tiếp theo là số nguyên dương ~1 \le q \le 10000~.
• ~q~ dòng tiếp theo dòng thứ ~i~ gồm số nguyên dương ~1 \le x_i \le n~ và ~1 \le y_i \le C~.

Output

• In ra ~q~ dòng thời gian tối thiểu cần phục vụ khách hàng.

Sample Test

Input:

8
1 2
1 3
2 7
2 8
3 4
4 5
4 6
4
1 2 4 2 3 1 3 2
8
1 4
2 4
3 4
4 4
5 4
6 4
7 4
8 4

Output:

1
2
0
1
2
2
3
3

Khi mua xiên que về, Suika nhận ra là vẫn chưa có rượu. Có ~n~ cửa hàng bán rượu và có ~m~ con đường nối trực tiếp giữa 2 cửa hàng nào đó. Việc mua rượu ở cửa hàng ~i~ sẽ tốn ~a_i~ sức lực, việc đi qua con đường thứ ~i~ sẽ tốn ~w_i~ sức lực. Hỏi với mỗi cửa hàng, nếu Suika xuất phát từ cửa hàng đó thì để mua rượu và quay lại đúng cửa hàng đó sẽ tốn bao nhiêu sức lực, nói cách khác với mỗi cửa hàng ~i~, hãy tìm với ~d(i, j)~ là đường đi ngắn nhất giữa cửa hàng ~i~ và ~j~.

Input

• Dòng đầu tiên gồm số tự nhiên ~1 \le n \le 10^5~ và ~1 \le m \le 10^5~.
• ~m~ dòng tiếp theo gồm 3 số nguyên ~u_i~, ~v_i~, ~w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^9 )~, đảm bảo không có khuyên và cạnh lặp.
• Dòng tiếp theo gồm ~n~ nguyên ~1 \le a_i \le 10^9~.

Output

• In ra ~n~ số tương ứng với ~n~ cửa hàng.

Sample Test

Input:

3 3
1 2 1
2 3 1
1 3 1
30 10 20

Output:

12 10 12