Background

Translated from Problem E of NERC 2018.

Problem Description

Elma is learning chess.

Elma is a beginner, and she does not really understand how to play chess yet. To help her understand chess better, her grandmother asks her to make $n$ moves on a board (as shown below). In each move, she can move horizontally or vertically by any number of squares, and each square can be visited at most once, so that she goes from a1 to h8.

Input Format

Input one integer $n(2 \leq n \leq 63)$, which means the total number of moves you need to make.

Output Format

Output one feasible solution, and make sure that the squares you have stayed on are not repeated.

4

a1 f1 c1 c8 h8

Hint

For all testdata, it is guaranteed that $2 \leq n \leq 63$, and that there exists at least one legal solution.

Translated by ChatGPT 5