Профессор Р. в свободное время увлекается шахматами, а его любимой математической задачей является задача о ходе коня. Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу. В терминах теории графов, данная задача идентична задаче поиска гамильтонова пути в графе. Для доски $$$8 \times 8$$$ количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно $$$13~267~364~410~532$$$. Количество всех незамкнутых маршрутов (с учётом направления обхода) равно $$$19~591~828~170~979~904$$$.
На рисунке ниже показан один из возможных маршрутов коня на доске (числами от 1 до 64 пронумерованы ходы):
Профессора Р. заинтересовали магические маршруты. Назовём маршрут коня магическим, если суммы номеров ходов в каждом столбце и каждой строке одинаковы (для доски размера $$$8 \times 8$$$ это значение равно 260). Профессор Р. придумал следующую задачу: из магического маршрута коня удаляется некоторое количество ходов, требуется восстановить любой маршрут, который содержит неудалённые ходы именно в таком порядке, в котором они расположены на доске.
Помогите профессору – напишите программу, которая найдёт магический маршрут, удовлетворяющий условиям.
Ввод содержит $$$8$$$ строк, каждая из которых содержит ровно $$$8$$$ чисел, разделённых пробелом. Если число положительное, то оно означает номер хода, на котором конь должен посетить эту клетку, если оно равно $$$-1$$$, это означает, что клетка может быть посещена на произвольном ходу. Гарантируется, что шаг с номером 1 на доске всегда присутствует, а также то, что решение всегда существует.
Выведите $$$8$$$ строк по $$$8$$$ чисел в каждой с заполненными полями.
Если задача имеет несколько решений, можно вывести любое из них.
1 48 -1 -1 33 -1 63 1830 51 -1 3 -1 -1 -1 -1-1 -1 -1 -1 15 -1 -1 -1-1 -1 -1 45 -1 -1 36 -1-1 -1 25 -1 9 -1 21 60-1 -1 -1 -1 24 57 12 -1-1 6 -1 -1 39 -1 -1 -154 -1 42 -1 -1 -1 -1 -1
1 48 31 50 33 16 63 18 30 51 46 3 62 19 14 35 47 2 49 32 15 34 17 64 52 29 4 45 20 61 36 13 5 44 25 56 9 40 21 60 28 53 8 41 24 57 12 37 43 6 55 26 39 10 59 22 54 27 42 7 58 23 38 11
Полю из примера соответствует следующий рисунок:
