背景

翻译自 NERC 2018 E 题。

题目描述

Elma 正在学习象棋。

Elma 是个新手，她还不特别了解象棋是如何下的，所以，为了更好地让她了解象棋，她的奶奶让她从一个棋盘（如下图）中进行 $n$ 次移动，每次移动只能是水平或垂直地移动若干个格子的，且每个点只能到达一次，使得从 a1 到 h8 处。

输入格式

输入一个数 $n(2 \leq n \leq 63)$，表示你一共需要走的步数。

输出格式

给出一种可行方案且保证停留过的点不重复。

4

a1 f1 c1 c8 h8

提示

对于所有数据保证 $2 \leq n \leq 63$ 且保证存在至少一种合法方案。