Занятие 20

Однажды Алиса и Боб решили поиграть в шахматы, но обнаружили, что многие фигуры отсутствуют. Тогда они придумали другую игру, для которой были нужны только часы, шахматная доска и ферзь. Правила игры достаточно просты. Первый игрок ставит ферзя на любую клетку доски. Затем игроки по очереди ходят ферзем, начиная со второго игрока. Ферзь может ходить на любое количество клеток по горизонтали, вертикали или диагонали. Если игрок поставит ферзя на клетку, где ферзь уже бывал, то игрок проигрывает. Игра может закончиться и вничью, только если ферзь уже побывал на всех клетках шахматной доски, но игрок может поставить ферзя на стартовую клетку.

Пусть известно, что игра закончилась вничью и известны ходы, сделанные первым игроком. Восстановите ходы второго игрока.

Во вводе содержится одна строка с ходами первого игрока, разделенными пробелом. Горизонталь обозначается цифрой, а вертикаль – буквой от a до h.

Вывести в аналогичной форме один (любой) из вариантов ходов, сделанных вторым игроком, при котором игра заканчивается вничью.

a8 a7 c4 d1 b4 a1 a3 c2 b3 b8 c5 d8 b7 c7 d2 d3 h5 e1 h1 f3 f2 g2 e6 f4 g6 e4 f8 g7 e8 g5 h2 h3

a5 a6 a4 b1 c3 a2 c1 b2 b5 d6 b6 c8 c6 d7 d4 d5 e5 h4 f1 e2 g1 g4 e3 g3 f5 e7 f6 f7 g8 h6 h7 h8