Chỉ lấy từ 3 kí tự A, B, C. Hãy tạo tất cả các xâu có độ dài ~ n ~ ~ (1 ≤ n < 15 ) ~ và không chứa xâu con ‘ABC’.

Dữ liệu vào

• Số nguyên dương ~ n ~

Kết quả

• Mỗi xâu kết quả ghi trên một dòng, sắp xếp theo thứ tự từ điển.

Ràng buộc

Ví dụ:

Input 1

3 

Output 1

AAA                             
AAB                             
AAC                             
ABA                             
ABB                             
ACA                             
ACB                             
ACC                             
BAA                             
BAB                             
BAC                             
BBA                             
BBB                             
BBC                             
BCA                             
BCB                             
BCC                             
CAA                             
CAB                             
CAC                             
CBA                             
CBB                             
CBC                             
CCA                             
CCB                             
CCC