Bài tập

Trang trại của Sắn có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày. Trang trại có hai máy vắt sữa. Mỗi con bò phải được đưa vào đúng một trong hai máy, và để hai máy chạy công suất như nhau, tổng lượng sữa của các con bò ở máy 1 phải bằng tổng lượng sữa của các con bò ở máy 2.

Một cách xếp là dãy \(x_1 x_2 \dots x_n\) với \(x_i \in \{1, 2\}\), trong đó \(x_i\) là số hiệu máy dành cho con bò thứ \(i\). Hãy liệt kê tất cả các cách xếp thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

• Nếu không có cách xếp nào, in ra -1.
• Ngược lại, mỗi dòng in một cách xếp dưới dạng xâu \(n\) chữ số \(x_1 x_2 \dots x_n\) viết liền nhau (không có dấu cách). Các cách xếp được in theo thứ tự từ điển tăng dần (so sánh như xâu ký tự).

Constraints

• \(1 \le n \le 20\)
• \(1 \le a_i \le 10^9\)

Sample Input

5
1 3 2 2 4

Sample Output

11122
11212
22121
22211

Explanation

Tổng sữa là \(12\), mỗi máy phải vắt được \(6\). Chẳng hạn cách 11122: máy 1 nhận các con \(1,2,3\) (\(1+3+2=6\)), máy 2 nhận các con \(4,5\) (\(2+4=6\)).

Sắn có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày, và hai chuồng bò. Mỗi con bò được nhốt vào chuồng thứ nhất, chuồng thứ hai hoặc không được nhốt vào chuồng nào. Yêu cầu: tổng lượng sữa của chuồng thứ nhất bằng tổng lượng sữa của chuồng thứ hai. Bò không có chuồng sẽ không cho sữa nữa.

Sắn muốn tổng lượng sữa thu được (của cả hai chuồng cộng lại) là lớn nhất có thể.

Hãy tìm lượng sữa lớn nhất đó, đồng thời liệt kê mọi tập bò bị bỏ ngoài chuồng mà vẫn đạt được lượng sữa lớn nhất (hai cách chia khác nhau nhưng có cùng tập bò bị bỏ ngoài chỉ được tính một lần). Cho phép để trống cả hai chuồng.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

• Dòng đầu tiên: lượng sữa lớn nhất thu được.
• Các dòng tiếp theo: mỗi dòng là một tập bò bị bỏ ngoài chuồng (liệt kê số thứ tự các con bò theo thứ tự tăng dần, cách nhau một dấu cách). Các tập được in theo thứ tự từ điển tăng dần (so sánh từng số nguyên, dãy ngắn hơn là tiền tố của dãy dài hơn thì đứng trước).
• Nếu tất cả bò đều được nhốt vào chuồng thì chỉ in đúng một dòng OK thay cho danh sách tập.
• Nếu không thể nhốt con nào (lượng sữa lớn nhất là \(0\)) thì tập bò bị bỏ ngoài chỉ có một, gồm tất cả các con bò.

Constraints

• \(1 \le n \le 15\)
• \(1 \le a_i \le 10^9\)

Sample Input 1

7
4 6 10 3 7 5 2

Sample Output 1

34
4

Sample Input 2

6
2 3 3 5 9 4

Sample Output 2

26
OK

Explanation

Ở ví dụ 1 tổng sữa là \(37\) (lẻ) nên phải bỏ ra ít nhất một con; bỏ con thứ \(4\) (\(3\) đơn vị) còn lại \(34\), chia được thành hai chuồng \(17 + 17\) (ví dụ \(4+6+7\) và \(10+5+2\)). Ở ví dụ 2 cả sáu con đều nhốt được: \(2+3+3+5 = 13 = 9+4\).

Trang trại của Sắn có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày. Sắn vừa xây hai chuồng bò mới và muốn nhốt bò vào hai chuồng sao cho tổng lượng sữa của các con bò trong chuồng thứ nhất bằng tổng lượng sữa của các con bò trong chuồng thứ hai. Mỗi con bò được nhốt vào tối đa một chuồng; những con bò không được nhốt vào chuồng nào coi như bị "thừa".

Sắn không muốn bỏ phí con bò nào nên muốn số con bò bị thừa là ít nhất. Hãy tính số con bò thừa tối thiểu. (Cho phép để trống cả hai chuồng, khi đó tổng của hai chuồng cùng bằng \(0\) và mọi con bò đều thừa.)

Input

• Dòng đầu tiên gồm số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

In ra một số nguyên duy nhất là số con bò thừa tối thiểu.

Constraints

• \(1 \le n \le 15\)
• \(1 \le a_i \le 10^9\)

Sample Input

7
10 4 6 3 3 9 12

Sample Output

1

Explanation

Tổng lượng sữa là \(47\) (số lẻ) nên chắc chắn phải bỏ ra ít nhất một con. Bỏ con thứ \(6\) (\(9\) đơn vị) ta còn \(38\), chia được thành chuồng một gồm các con \(10, 3, 6\) và chuồng hai gồm \(12, 4, 3\) với cùng tổng \(19\).

Một người nông dân có \(N\) luống rau, luống thứ \(i\) cho thu hoạch \(a_i\) gam. Ông muốn chọn một tập luống giao cho xe A và một tập luống khác giao cho xe B sao cho:

• Mỗi tập gồm ít nhất một luống, hai tập không có luống chung;
• Tổng lượng rau của hai xe bằng nhau.

Hãy đếm số cách chọn cặp \((\text{tập cho xe A}, \text{tập cho xe B})\). Cặp có thứ tự: đổi vai trò hai xe cho nhau được tính là một cách khác.

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số nguyên \(a_1, \dots, a_N\).

Output

• In ra số cách chọn.

Constraints

• \(1 \le N \le 22\)
• \(1 \le a_i \le 10^8\)

Sample Input 1

5
2 3 5 1 4

Sample Output 1

14

Sample Input 2

2
7 7

Sample Output 2

2

Explanation

Ở ví dụ 2 có hai cách: luống 1 cho xe A và luống 2 cho xe B, hoặc ngược lại.