Tháp Hà Nội

Trò chơi tháp Hà Nội là trò chơi nổi tiếng với những chiếc đĩa có kích thước đôi một khác nhau, có lỗ ở giữa, nằm xuyên trên ba chiếc cọc A, B, C.

Trò chơi bắt đầu bằng trạng thái các đĩa được chồng lên nhau ở cọc A, đĩa nhỏ nằm trên đĩa lớn, tức là đĩa nhỏ nhất nằm trên cùng, tạo ra một dạng hình nón. Yêu cầu của trò chơi là chuyển toàn bộ số đĩa từ cọc A sang cọc C, tuân theo các quy tắc sau:

• Chỉ sử dụng $3$ cọc để chuyển;
• Một lần chỉ được di chuyển một đĩa nằm trên cùng từ cọc này sang cọc khác;
• Một đĩa chỉ được đặt lên một đĩa lớn hơn.

Trong bài toán này, chúng ta sẽ có $n$ chiếc đĩa, đánh số từ $1$ đến $n$ theo thứ tự kích thước đĩa tăng dần, đĩa $1$ là đĩa có kích thước nhỏ nhất, đĩa $n$ là đĩa có kích thước lớn nhất. Ban đầu, các đĩa nằm rải rác ở ba cọc nhưng vẫn thỏa mãn điều kiện đĩa nhỏ nằm trên đĩa lớn và mục tiêu là chuyển toàn bộ đĩa thành một chồng đĩa ở cọc C.

Yêu cầu: Cho trạng thái của các đĩa nằm ở các cọc, hãy tìm cách chuyển toàn bộ đĩa thành một chồng đĩa ở cọc C. Số lần chuyển đĩa không được vượt quá $2^n-1$ (luôn tồn tại cách chuyển như vậy). Nếu có nhiều cách chuyển thỏa mãn, in ra một cách bất kỳ.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $n$;
• Dòng thứ hai chứa một xâu gồm $n$ kí tự, kí tự thứ $i$ ($i=1,2,\dots ,n$) bằng 'A' hoặc 'B' hoặc 'C' cho biết đĩa thứ $i$ đang nằm ở cọc A hoặc cọc B hoặc cọc C.

Dữ liệu ra

• Dòng đầu chứa số nguyên $s$ là số lần chuyển đĩa ($0\le s\le 2^n-1$);
• Dòng thứ $j$ ($j=1,2,\dots ,s$) trong $s$ dòng tiếp theo, mỗi dòng gồm đúng hai kí tự mô tả một thao tác chuyển đĩa. Cụ thể, kí tự thứ nhất là tên cọc chứa đĩa cần chuyển, kí tự thứ hai là tên cọc mà đĩa chuyển tới.

Ràng buộc

• $1\le n\le 20$.

Subtasks

• Có $20\%$ số test ứng với $20\%$ số điểm của bài có $n=3$;
• Có $30\%$ số test khác ứng với $30\%$ số điểm của bài có $n\le 10$ và cả $n$ đĩa ban đầu ở cọc A;
• Có $20\%$ số test khác ứng với $20\%$ số điểm của bài có $n\le 10$;
• Có $30\%$ số test còn lại với $30\%$ số điểm còn lại của bài có $n\le 20$.

Ví dụ