시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 16 6 6 42.857%

문제

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 × 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 ≤ n ≤ 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

4 a1 f1 c1 c8 h8