Ông Rubik sau khi phát minh ra khối Rubik nổi tiếng toàn cầu, lại phát minh ra phiên bản hai chiều của nó - Bảng ma thuật (Magic Board). Đây là một tấm bảng có ô vuông kích thước bằng nhau:
1 2 3 4
8 7 6 5
Chúng ta biết rằng mỗi ô vuông của bảng ma thuật đều có một màu. loại màu này được biểu diễn bằng số nguyên dương đầu tiên. Có thể dùng một dãy số màu để biểu diễn trạng thái của bảng ma thuật, quy định bắt đầu từ góc trên bên trái của bảng, lấy các số theo chiều kim đồng hồ để tạo thành một dãy màu. Đối với trạng thái bảng ở hình trên, chúng ta dùng dãy số để biểu diễn. Đây là trạng thái cơ bản.
Có ba thao tác cơ bản, được ký hiệu bằng các chữ cái in hoa A, B, C (có thể thay đổi trạng thái của bảng thông qua các thao tác này):
A: Đổi chỗ hai hàng trên và dưới.
B: Chèn cột ngoài cùng bên phải vào vị trí ngoài cùng bên trái (dịch chuyển vòng sang phải).
C: Xoay 4 ô ở trung tâm bảng theo chiều kim đồng hồ.
Dưới đây là minh họa cho các thao tác trên trạng thái cơ bản:
A:
8 7 6 5
1 2 3 4
B:
4 1 2 3
5 8 7 6
C:
1 7 2 4
8 6 3 5
Đối với mỗi trạng thái có thể, cả ba thao tác cơ bản đều có thể sử dụng.
Bạn hãy lập trình tính toán chuỗi thao tác cơ bản ngắn nhất để chuyển từ trạng thái cơ bản sang trạng thái đặc biệt cho trước, và xuất ra chuỗi thao tác đó.
Dữ liệu:
Nhập vào duy nhất một dòng gồm số nguyên, cách nhau bởi dấu cách, biểu thị trạng thái đích.
Kết quả:
Dòng đầu tiên của file kết quả chứa một số nguyên, biểu thị độ dài của chuỗi thao tác ngắn nhất.
Dòng thứ hai là chuỗi thao tác đó (nếu có nhiều chuỗi cùng độ dài, chọn chuỗi có thứ tự từ điển nhỏ nhất).
Ví dụ:
Dữ liệu:
2 6 8 4 5 7 3 1
Kết quả:
7
BCABCCB
Giới hạn: Dữ liệu đầu vào đảm bảo tất cả các số đều là số nguyên từ đến .
