Bài toán Tháp Hà Nội (Tower of Hanoi) là bài toán đệ quy kinh điển:

Có ba cọc \(A, B, C\) và \(n\) đĩa kích thước khác nhau xếp ở cọc \(A\) (đĩa to dưới, đĩa nhỏ trên). Cần chuyển toàn bộ \(n\) đĩa từ cọc \(A\) sang cọc \(C\), sử dụng cọc \(B\) làm trung gian.

Quy tắc: mỗi lần chỉ được di chuyển một đĩa, đĩa to không được đặt lên đĩa nhỏ.

Hãy in ra các bước di chuyển.

Input

Một dòng duy nhất chứa số nguyên \(n\) (\(1 \le n \le 10\)).

Output

In ra các bước di chuyển, mỗi bước trên một dòng theo định dạng X -> Y (chuyển một đĩa từ cọc X sang cọc Y).

Example

3

Output:

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C