Trong làng Omega có một 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 ba người con đã đến tuổi trưởng thành đến và 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ãy tìm tất cả các cách chia đều \(n\) thửa ruộng cho ba người con sao cho tổng diện tích ruộng mỗi người nhận được là bằng nhau và các thửa ruộng được chia phải giữ nguyên diện tích.

Input

• Dòng thứ nhất ghi số nguyên dương \(n\) là số thửa ruộng của phú ông đem chia.
• Dòng thứ hai ghi \(n\) số nguyên dương \(a_i\) là diện tích của thửa ruộng thứ \(i\).

Output

• Dòng thứ nhất ghi số cách chia tìm được. Nếu không thể chia được thì ghi \(-1\).
• Các dòng sau (nếu có cách chia), mỗi dòng ghi một xâu độ dài \(n\) mô tả một cách chia: ký tự thứ \(i\) là A nếu thửa ruộng thứ \(i\) chia cho người thứ nhất, là B nếu chia cho người thứ hai, và là C nếu chia cho người thứ ba. Các cách chia cần được liệt kê theo thứ tự từ điển của xâu ký tự.

Constraints

• \(1 \le n \le 20\)
• \(100 \le a_i \le 5000\)

Example

5
100 200 250 50 300

6
AABBC
AACCB
BBAAC
BBCCA
CCAAB
CCBBA

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 12\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.