문제

Elma is learning chess figures.

She learned that a rook can move either horizontally or vertically. To enhance her understanding of rook movement Elma's grandmother gave Elma an $8 \times 8$ chess board and asked her to find a way to move the rook from a1 to h8 making exactly $n$ moves, so that all visited cells are different.

A visited cell is the initial cell a1 and each cell on which the rook lands after a move.

입력

The input contains a single integer $n$ ($2 \le n \le 63$) — the desired number of moves.

출력

Output a space-separated list of $n+1$ visited cells in the order they are visited by the rook. All cells must be different. The list should start with a1 and end with h8. A solution always exists.

예제 입력 1

4

예제 출력 1

a1 f1 c1 c8 h8