16664번 - Easy Chess 스페셜 저지다국어

문제

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.

제한

힌트