В игре Судоку вы получаете большой 9×9 квадрат, разделённый на меньшие 3×3 подквадратов. Например,
Зная расположение некоторых цифр в квадрате, ваша цель состоит в определении местоположения остальных цифр таким образом, что все цифры от 1 по 9 появляются только один раз:
(1) в каждом из девяти 3×3 подквадратов
(2) в каждой из девяти строк, и
(3) в каждом из девяти столбцов.
Входные данные будут содержать несколько тестов. Каждый тест состоит из одной строки, содержащей 81 символ, которые представляют 81 квадратов сетки Судоку, с учётом каждой строки только один раз. Каждый символ является либо цифрой (от 1 до 9) или точкой (используется для обозначения незаполненных мест). Можно считать, что каждая головоломка, полученная на входе, будет иметь единственное решение. Конец файла обозначается строкой, содержащей слово "end".
Для каждого теста вывести в отдельной строке завершённую головоломку Судоку.