Cho 2 số nguyên dương A, B (A ≤ B). Tính tổng các chữ số có mặt trong các số nguyên từ A đến B.

Input

Hai số A, B.

Output

Tổng tìm được.

Ràng buộc: 1 ≤ A < B ≤ 10^18.

Ví dụ:

Giải thích: 38 = 5 + 6 + 7 + 8 + 9 + 1+0 + 1+1

x ≤ 10^6

Đề bài

Ví dụ

Input

2
3
4

Output

6
12

Nguồn

Cho một đồ thị liên thông vô hướng gồm N-1 đỉnh. Với mỗi đỉnh v sẽ có một trọng số ~a_v~.

Gọi d(u, v) là khoảng cách giữa hai đỉnh u và v. Khoảng cách giữa hai đỉnh bất kỳ là số lượng cạnh trên đường đi đơn giữa chúng.

Chi phí trên cây được tính bằng tổng các tích giữa khoảng cách từ đỉnh gốc đến các đỉnh khác với trọng số của đỉnh đó.

Hay nói cách khác, nếu ta lấy một đỉnh v bất kỳ làm gốc, thì chi phí trên cây sẽ là: ~C=sum( d(v,i) * a_i),i=1..N ~.

Yêu cầu: Tìm giá trị của ~C_{max}~ là chi phí trên cây lớn nhất khi chọn một đỉnh v nào đó làm gốc.

Dữ liệu:

• Dòng đầu tiên chứa một số nguyên N (~1≤N≤2*10^5~) là số đỉnh trong cây.
• Dòng thứ hai chứa N số nguyên ~a_1, a_2, ..., a_N~ (~1≤a_i≤2*10^5~) với ~a_i~ là trọng số của đỉnh i.
• N-1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1≤u, v≤N, u≠v) thể hiện cho một cạnh trong cây. Mỗi cặp số nguyên u, v chỉ xuất hiện một lần.

Kết quả:

Đưa ra một số nguyên duy nhất là ~C_{max}~.

Ví dụ:

Input

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

Output

121

Giải thích:

Chọn đỉnh 3 làm gốc, ta có tổng chi phí lớn nhất là: ~2*9+1*4+0*1+3*7+3*10+4*1+4*6+4*5=18+4+0+21+30+4+24+20=121~.

Ví dụ:

Input

3

Output

4

Hai số nguyên a và b được gọi là tương thích với nhau nếu kết quả của phép toán AND của chúng bằng 0, nghĩa là a & b  = 0. Ví dụ: các số 90 (~1011010_2~) và 36 (~100100_2~) tương thích, vì ~1011010_2~ & ~100100_2~  = ~0_2~; nhưng số 3 (~11_2~) và 6 (~110_2~) không tương thích, vì ~11_2~ & ~110_2~ = ~10_2~.

Cho dãy các số nguyên ~a_1,  a_2, ..., a_n~ .

Yêu cầu: Với mỗi số ~a_i~ (1≤i≤n), tìm phần tử ~a_j~ sao cho ~a_i~ tương thích với ~a_j~. Nếu có nhiều kết quả, bạn in ra kết quả bất kỳ. Trường hợp không tìm được số ~a_j~ tương thích với ~a_i~ thì in ra số ~-1~.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên n ( 1 ≤  n  ≤ ~10^6~ ) - số phần tử trong dãy đã cho.
• Dòng thứ hai chứa n số nguyên được phân tách bằng dấu cách ~a_1, a_2,..., a_n~ ( ~1 ≤  a_i  ≤ 4.10^6~ ) - các phần tử của dãy đã cho. Các số trong dãy có thể trùng nhau.

Kết quả ra:

In ra n số nguyên.

Ví dụ:

Input

5
10 6 9 8 2

Output

-1 8 2 2 8