Cho một cây nhị phân với ~n~ nút (đánh số từ ~1~ đến ~n~). Mỗi nút có một giá trị nguyên ~A_i~. Một cây được gọi là "cân bằng" nếu:

1. Cân bằng cấu trúc: Với mỗi nút, độ chênh lệch chiều cao giữa cây con trái và cây con phải không quá ~1~.
2. Cân bằng giá trị: Với mỗi nút, tổng giá trị của cây con trái và cây con phải phải bằng nhau.

Bạn cần tìm số lượng cây con (subtree) cân bằng trong cây đã cho.

Note: Giả sử Input chỉ có một Testcase duy nhất.

Input Specification

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(1 \le A_i \le 10^9)~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~, ~v~ ~(1 \le u, v \le n)~ biểu thị một cạnh nối giữa nút ~u~ và nút ~v~.

Output Specification

• In ra một số nguyên duy nhất: số lượng cây con cân bằng.

Constrains

• ~1 \le n \le 10^5~.
• ~1 \le A_i \le 10^9~.
• Cây đã cho là cây nhị phân hợp lệ.
• Các cạnh được mô tả dưới dạng danh sách cạnh.

Sample Cases

Input #1:

5
1 2 3 4 5
1 2
1 3
2 4
2 5

Output #1:

3

Explanation #1:

Các cây con cân bằng là:

• Nút ~4~ (cây con trái ~=~ phải ~=~ ~0~, giá trị ~=~ ~4~).
• Nút ~5~ (cây con trái ~=~ phải ~=~ ~0~, giá trị ~=~ ~5~).
• Nút ~2~ (cây con trái ~=~ ~4~, phải ~=~ ~5~, tổng giá trị bằng nhau ~=~ ~9~).

Input #2:

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

Output #2:

7

Explanation #2:

Tất cả các nút đều tạo thành cây con cân bằng vì có cấu trúc đối xứng và giá trị bằng nhau.

Input #3:

3
1 2 3
1 2
1 3

Output #3:

2

Explanation #3:

Các cây con cân bằng là nút 2 và nút 3 (cây con trái = phải = 0).

Cho một mảng ~A~ gồm ~n~ số nguyên và một số nguyên ~k~. Bạn cần tìm mảng con tăng dần có độ dài chính xác ~k~ sao cho:

1. Các phần tử trong mảng con phải tăng dần nghiêm ngặt ~(A[i] < A[i + 1])~.
2. Tổng của mảng con phải chia hết cho ~k~.
3. Nếu có nhiều mảng con thỏa mãn, chọn mảng con có tổng lớn nhất.

Nếu không tồn tại mảng con nào thỏa mãn điều kiện, in ra -1.

Note: Giả sử Input chỉ có một Testcase duy nhất.

Input Specification

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \le k \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(-10^9 \le A_i \le 10^9)~.

Output Specification

• In ra một số nguyên duy nhất: tổng của mảng con tối ưu thỏa mãn điều kiện, hoặc -1 nếu không tồn tại.

Constrains

• ~1 \le k \le n \le 10^5~.
• ~-10^9 \le A_i \le 10^9~.

Sample Cases

Input #1:

6 3
1 2 3 4 5 6

Output #1:

9

Explanation #1:

Mảng con ~[2, 3, 4]~ tăng dần, có độ dài ~3~, và tổng ~9~ chia hết cho ~3~. Đây là mảng con tối ưu.

Input #2:

5 2
5 4 3 2 1

Output #2:

-1

Explanation #2:

Không có mảng con tăng dần nào có độ dài ~2~ vì mảng giảm dần.

Input #3:

7 4
1 3 5 7 2 4 6

Output #3:

18

Explanation #3:

Mảng con ~[1, 3, 5, 7]~ tăng dần, có độ dài ~4~, và tổng ~16~ chia hết cho ~4~. Nhưng mảng con ~[2, 4, 6, 8]~ có tổng ~20~ cũng chia hết cho ~4~ và lớn hơn.

Cho một mảng ~A~ gồm ~n~ số nguyên và một số nguyên ~k~. Bạn cần tìm tổng con liên tiếp có tổng lớn nhất sao cho:

1. Độ dài của dãy con phải chính xác bằng ~k~.
2. Tổng của dãy con phải chia hết cho ~k~.

Nếu không tồn tại dãy con nào thỏa mãn điều kiện, in ra -1.

Note: Giả sử Input chỉ có một Testcase duy nhất.

Input Specification

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \le k \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(-10^9 \le A_i \le 10^9)~.

Output Specification

• In ra một số nguyên duy nhất: tổng con liên tiếp tối ưu thỏa mãn điều kiện, hoặc -1 nếu không tồn tại.

Constrains

• ~1 \le k \le n \le 10^5~.
• ~-10^9 \le A_i \le 10^9~.

Sample Cases

Input #1:

5 3
1 2 3 4 5

Output #1:

9

Explanation #1:

Dãy con ~[2, 3, 4]~ có tổng ~= 9~, độ dài ~= 3~, và ~9~ chia hết cho ~3~. Đây là dãy con tối ưu.

Input #2:

4 2
-1 -2 -3 -4

Output #2:

-1

Explanation #2:

Không có dãy con nào có độ dài ~2~ và tổng chia hết cho ~2~.

Input #3:

6 3
1 1 1 1 1 1

Output #3:

3

Explanation #3:

Dãy con ~[1, 1, 1]~ có tổng ~= 3~, độ dài ~= 3~, và ~3~ chia hết cho ~3~.

Cho một chuỗi số nguyên ~A~ gồm ~n~ phần tử. Một chuỗi con được gọi là "đối xứng" nếu khi đọc từ trái sang phải và từ phải sang trái đều cho cùng một dãy số.

Bạn cần tìm chuỗi con đối xứng có tổng lớn nhất trong chuỗi ~A~.

Note: Giả sử Input chỉ có một Testcase duy nhất.

Input Specification

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(-10^9 \le A_i \le 10^9)~.

Output Specification

• In ra một số nguyên duy nhất: tổng của chuỗi con đối xứng có tổng lớn nhất.

Constrains

• ~1 \le n \le 10^5~.
• ~-10^9 \le A_i \le 10^9~.

Sample Cases

Input #1:

5
1 2 3 2 1

Output #1:

9

Explanation #1:

Chuỗi con ~[1, 2, 3, 2, 1]~ là đối xứng và có tổng ~= 9~, đây là chuỗi con đối xứng có tổng lớn nhất.

Input #2:

4
-1 2 2 -1

Output #2:

2

Explanation #2:

Chuỗi con ~[2, 2]~ là đối xứng và có tổng ~= 4~, nhưng chuỗi con ~[-1, 2, 2, -1]~ có tổng ~= 2~ và cũng đối xứng. Ta chọn chuỗi có tổng lớn hơn.