Bài tập

Cho một dãy gồm \(N\) số nguyên dương. Hãy kiểm tra xem có thể chia toàn bộ các số của dãy thành hai nhóm (mỗi số thuộc đúng một nhóm) sao cho tổng các số ở hai nhóm bằng nhau hay không.

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng đầu chứa \(N\); dòng sau chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

Với mỗi bộ dữ liệu in ra YES nếu chia được, ngược lại in NO.

Constraints

• \(1 \le T \le 20\)
• \(1 \le N \le 100\)
• \(1 \le A_i \le 1000\)

Sample Input

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

Sample Output

YES
NO
NO

Explanation

Bộ 1: tổng \(22\), chia \(\{2,3,6\}\) và \(\{7,4\}\) đều được \(11\) nên YES. Bộ 2: tổng \(15\) là số lẻ nên NO. Bộ 3: chỉ có một số nên không thể chia đều, NO.

Sắn có một dãy \(N\) món đồ chơi xếp trong tủ theo thứ tự mua, món thứ \(i\) có giá \(v_i\). Sau khi thua cược, Sắn phải chia đồ chơi cho Mì theo cách sau: Sắn chọn trước một số nguyên \(x \in \{1, 2, 3\}\), sau đó hai bạn lần lượt lấy đồ chơi từ đầu dãy: Sắn lấy \(x\) món đầu tiên, Mì lấy \(x\) món tiếp theo, rồi lại đến Sắn \(x\) món, ... cho đến khi hết đồ (nếu lượt cuối còn ít hơn \(x\) món thì người đó lấy hết số còn lại).

Sắn muốn phần của mình có tổng giá trị lớn nhất có thể. Hãy chọn \(x\) tối ưu và in ra tổng giá trị đó.

Input

• Dòng đầu chứa số bộ test \(T\).
• Mỗi bộ test gồm hai dòng: dòng thứ nhất là \(N\), dòng thứ hai gồm \(N\) số nguyên \(v_1, \dots, v_N\).

Output

Với mỗi bộ test in một dòng: tổng giá trị lớn nhất Sắn có thể nhận.

Constraints

• \(1 \le T \le 10\)
• \(1 \le N \le 10^5\)
• \(1 \le v_i \le 10^9\)

Sample Input

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

Sample Output

15
26

Explanation

Bộ test 1: với \(x = 3\) Sắn lấy \(9, 2, 4\) được \(15\) (Mì lấy \(6, 1\)); các giá trị \(x = 1, 2\) chỉ cho \(14\) và \(12\). Bộ test 2: với \(x = 3\) Sắn lấy \(3, 8, 8\) và \(7\), tổng \(26\).

Cho dãy \(A\) gồm \(N\) số nguyên dương. Với mỗi truy vấn \((u, v)\), xét đoạn \(A_u, A_{u+1}, \dots, A_v\). Ta cắt đoạn này tại một vị trí nào đó thành hai phần: phần đầu (tiền tố) và phần sau (hậu tố); một trong hai phần được phép rỗng. Hãy tìm giá trị nhỏ nhất của \(|S_1 - S_2|\), với \(S_1\), \(S_2\) lần lượt là tổng của hai phần.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, \dots, A_N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một truy vấn.

Output

In ra \(Q\) dòng, dòng thứ \(i\) là đáp án của truy vấn thứ \(i\).

Constraints

• \(1 \le N, Q \le 10^5\).
• \(1 \le A_i \le 10^9\).
• \(1 \le u \le v \le N\).

Sample Input

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

Sample Output

0
1

Explanation

Truy vấn \((1,4)\): đoạn \(2,7,1,8\) chia thành \((2,7)\) và \((1,8)\), cùng tổng \(9\), chênh lệch \(0\). Truy vấn \((3,6)\): đoạn \(1,8,2,8\) chia thành \((1,8)\) và \((2,8)\) có tổng \(9\) và \(10\), chênh lệch \(1\).

Cho hai xâu \(A\) và \(B\) gồm các chữ cái thường. Gọi \(L\) là độ dài xâu con chung dài nhất của \(A\) và \(B\).

Ta muốn chèn đúng một chữ cái thường vào một vị trí nào đó của \(A\) (đầu xâu, cuối xâu hoặc giữa hai ký tự liên tiếp; xâu \(A\) có \(|A| + 1\) vị trí chèn) sao cho độ dài xâu con chung dài nhất của xâu mới và \(B\) trở thành \(L + 1\).

Hãy đếm số cặp (vị trí chèn, chữ cái được chèn) thoả mãn. Hai cặp có vị trí khác nhau luôn được tính là hai cách khác nhau, kể cả khi xâu thu được giống nhau.

Input

• Dòng thứ nhất chứa xâu \(A\).
• Dòng thứ hai chứa xâu \(B\).

Output

In ra một số nguyên là số cách chèn thoả mãn.

Constraints

• \(1 \le |A|, |B| \le 1010\)
• Hai xâu chỉ gồm chữ cái tiếng Anh viết thường.

Sample Input

abc
cbad

Sample Output

9

Explanation

Xâu con chung dài nhất của abc và cbad có độ dài \(1\). Có \(9\) cách chèn để độ dài này tăng lên \(2\), chẳng hạn chèn d vào cuối abc được abcd (có xâu con chung ad), hoặc chèn b vào đầu abc được babc (có xâu con chung ba).