Trong làng Omega có 1 phú ông rất giầu có. Tài sản của ông rất nhiều trâu, bò, ruộng vườn. Một hôm ông gọi 3 người con đã đến tuổi trưởng thành đến ông chia cho một số ruộng để làm ăn. Ông có hàng trăm mẫu ruộng nhưng ông chỉ chọn ~ n ~ thửa ruộng để chia, thửa thứ ~ i ~ có diện tích ~ a_i ~ ~ m^2 ~. Hỏi rằng phú ông có bao nhiêu cách chia đều ~ n ~ thửa ruộng cho 3 con sao cho các thửa ruộng được chia phải giữ nguyên diện tích.

Dữ liệu vào

• Dòng 1: ghi số ~ n ~ là số thửa ruộng của phú ông đem chia ~ (1≤n≤18) ~
• Dòng 2: ghi các số ~ a_i ~ là diện tích của thửa ruộng thứ ~ i ~ ~ (1≤a_i≤5000) ~.

Kết quả

• Dòng thứ nhất ghi số cách chia, nếu không thể chia được thì ghi -1.
• Các dòng sau trong trường hợp chia được, mỗi dòng là 01 cách chia với quy ước người thứ nhất có tên là “A”, người thứ hai có tên là “B”, người thứ ba có tên là “C” và phải tương ứng với thứ tự của các thửa ruộng được chia. Các phương án chia được liệt kê theo thứ tự tăng dần.

Ràng buộc

Ví dụ:

Input 1

5
100 200 250 50 300 

Output 1

6
AABBC
AACCB
BBAAC
BBCCA
CCAAB
CCBBA