THPT Chuyên Bến Tre

Người Ả rập xưa có một trò chơi đơn giản trên một bảng 3 * 3 như hình vẽ ở dưới đây:

Ban đầu, ở mỗi ô ghi một số nguyên từ 1 đến 9. Trên bảng này có 4 nút A, B, C, D. Bạn có thể dùng 4 nút này để xoay 4 ô xung quanh nó.

Lưu ý rằng ở hình trên, việc viết các số theo chiều ngang chỉ để hiểu rõ cách xoay, kết quả thực hiện các phép quay "Ad" là bảng số sau: 

4 1 3

5 6 9

7 2 8

Trò chơi này được thực hiện theo trình tự như sau:

• Từ trạng thái ban đầu, người chơi thứ nhất thực hiện một loạt các phép xoay
• Người chơi thứ hai phải dùng các phép xoay để đưa được về trạng thái ban đầu

Bạn được cho trước các phép xoay của người thứ nhất, hãy giúp người thứ hai tìm cách dùng ít phép xoay nhất để đưa trở lại trạng thái ban đầu.

Input

• Gồm một dòng ghi một xâu S thể hiện các phép xoay của người chơi thứ nhất
• Xâu chỉ gồm các ký tự A, B, C, D, a, b, c, d trong đó các ký tự in hoa tương ứng với các phép xoay cùng chiều kim đồng hồ và các ký tự in thường tương ứng với các phép xoay ngược chiều kim đồng hồ. Các phép xoay được thực hiện theo thứ tự lần lượt từ trái sang phải.

Output

• Ghi ra một xâu phương án gồm ít phép xoay nhất để đưa về vị trí ban đầu. Xâu được in ra theo định dạng tương tự như trong dữ liệu vào.
• Nếu có nhiều phương án thì đưa ra phương án có số thứ tự từ điển nhỏ nhất.

Example

Input:
Ad

Output:
Da

* Giới hạn

• 1 <= length(s) <= 10000
• Trong đó 60% test kết quả tối ưu không vượt quá 5 bước xoay