Hãy in ra tất cả các xâu độ dài ~n~ gồm ba kí tự A, B và C, sao cho không có hai kí tự liền nhau nào giống nhau.

Ví dụ, xâu ABBC không hợp lệ vì nó chứa hai kí tự B đứng cạnh nhau.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên ~n~.

Kết quả

In ra tất cả các xâu hợp lệ, mỗi xâu trên một dòng. Thứ tự in ra là tùy ý.

Ví dụ

Đầu vào:

2

Đầu ra:

AB
AC
BA
BC
CA
CB

Giải thích: Với ~n = 2~ có ~6~ xâu hợp lệ. Mọi thứ tự in đều được chấp nhận, nên BA AB CB BC AC CA cũng là một đáp án đúng.

Giới hạn

• ~1 \le n \le 10~

Số xâu hợp lệ là ~3 \cdot 2^{n-1}~, nhiều nhất là ~1536~ xâu khi ~n = 10~.