Cô giáo có N túi kẹo, túi thứ i có A_i viên kẹo. Cô muốn chia N túi kẹo này cho 2 đội học sinh sao cho đội nào cũng nhận được kẹo (không ai bị nhận 0 túi), và mỗi đội phải nhận nguyên cả túi (không được bóc lẻ túi ra). Yêu cầu quan trọng nhất là chênh lệch tổng số viên kẹo giữa hai đội phải là nhỏ nhất có thể. Hãy tính độ chênh lệch nhỏ nhất đó.

Input:

Dòng 1: N (1 <= N <= 20).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^5).

Output: Chênh lệch nhỏ nhất giữa hai đội.

Ví dụ:

Input:

4
1 5 11 5

Output:

0

(Giải thích: Đội 1 nhận túi 11. Đội 2 nhận túi 1, 5, 5. Tổng mỗi đội là 11, chênh lệch bằng 0).

Trên trục tọa độ Ox có N đoạn thẳng. Đoạn thẳng thứ i bắt đầu tại Li và kết thúc tại Ri. Hai đoạn thẳng được coi là có giao điểm nếu chúng có ít nhất một điểm chung (ví dụ đoạn [1, 3] và đoạn [3, 5] giao nhau tại 3). Bạn hãy đếm xem có tất cả bao nhiêu cặp đoạn thẳng có giao điểm với nhau.

Input:

Dòng 1: N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Li, Ri (1 <= Li <= Ri <= 10^9).

Output: Số lượng cặp đoạn thẳng giao nhau.

Ví dụ:

Input:

3
1 4
2 5
6 8

Output:

1

(Giải thích: Cặp (1, 4) và (2, 5) giao nhau).

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự "0" hoặc "1" Xâu v gọi là xâu con của w nếu xâu v có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu w. Ví dụ: xâu "010" có các xâu con là "O", "1", "0", "01", ' "10", , "010".

Cho trước một giá trị k, hãy đếm xem có bao nhiêu xâu con chứa đúng k ký tự "1"

INPUT:

• Dòng 1 chứa một số nguyên k (1 ≤ k ≤ 10^6)

• Dòng 2 chứa một xâu nhị phân có độ dài ≤ 10^6

OUTPUT:

• Một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Input:

2
01010

Output:

4

Bạn được cho một mảng gồm n số nguyên, và nhiệm vụ của bạn là tìm ba giá trị (tại ba vị trí khác nhau) sao cho tổng của chúng bằng x.

Input:

Dòng đầu tiên chứa hai số nguyên n và x — kích thước mảng và tổng cần tìm.

Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ — các giá trị trong mảng.

Output:

In ra ba số nguyên: chỉ số của ba phần tử tạo thành tổng x.

Nếu có nhiều đáp án, bạn có thể in ra bất kỳ một đáp án nào.

Nếu không có lời giải, in ra IMPOSSIBLE.

Ràng buộc:

~1 \le n \le 5000~

~1 \le x,a_i \le 10^9~

Ví dụ :

Input:

4 8
2 7 5 1

Output:

1 3 4

Cho hai xâu S và T. Hãy đếm số lượng dãy con của S bằng T.

Dữ liệu vào:

Dòng 1: Xâu S.

Dòng 2: Xâu T. (Độ dài S, T không quá 1000).

Dữ liệu ra:

Số lượng dãy con modulo 10^9 + 7.

Ví dụ:

Input:

rabbbit 
rabbit

Output:

3