Trò chơi tháp Hà Nội 2f là trò chơi tổng quát của tháp Hà Nội cổ điển gồm \(n\) đĩa với kích thước khác nhau và ba cọc \(A, B, C\). Một ma trận \(G\) thể hiện mối quan hệ được phép chuyển đĩa giữa các cọc (cọc \(x\) sang cọc \(y\) nếu \(G[x][y] = 1\)). Trò chơi bắt đầu bằng trạng thái các đĩa được chồng lên nhau ở cọc \(A\).

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 \(x\) sang cọc \(y\) nếu \(G[x][y] = 1\);
• Một đĩa chỉ được đặt lên một đĩa không nhỏ hơn.

Yêu cầu: Hãy tìm cách chuyển toàn bộ đĩa thành một chồng đĩa ở cọc \(C\).

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(n \le 15\));
• Tiếp theo là ba dòng, mỗi dòng ba số mô tả ma trận \(G\).

Output

• Dòng đầu chứa số nguyên \(s\) là số lần chuyển đĩa;
• 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.

Example

1
0 1 0
0 0 1
1 0 0

2
AB
BC