Japanski Junak

Akihise Wada is a Buddhist priest from Yokohama. That sounds ordinary at first, but Aki is also a passionate fan of Hajduk Split, a longtime member of Torcida, and a lover of Croatian culture. Rumor in the Split football circles says he is in direct contact with Marko Livaja after every match. This problem was inspired by the following (completely authentic) message exchange on Instagram.

Marko: 'Hey Aki, could you explain to me how your sudoku works? I don't understand any of it. . . '

Aki: 'Marko-san, solving sudoku puzzles is an ancient art. It deserves a whole lifetime.'

Marko: 'I'm not trying to become some grand master. I just want to finish these within 24 hours after training. My granny can solve them.'

Aki: 'Then you've already mastered cross-hatching, and you're good at it.'

Marko: 'Cross what? I'm the best at crosses.'

You've probably figured it out by now. Write a program that solves a sudoku puzzle using the cross-hatching method.

The goal of a sudoku puzzle is to place the numbers 1 to 9 on a 9 × 9 square board so that every row, every column, and every 3 × 3 block contains each of the nine numbers.

Cross-hatching works as follows. First, choose one of the nine numbers. For each place it appears on the board, mark its row, column, and 3 × 3 block as excluded for that number. Then look for a 3 × 3 block that does not yet contain that number and in which exactly one cell is still possible for it. Write the number in that cell.

You are given a partially filled board. Your task is to repeat cross-hatching to correctly fill as many empty cells as possible.

The initial board may be illegal, meaning a number may repeat within a row, column, or 3 × 3 block. It is also possible that during solving you reach a situation where a number cannot be placed in some block at all. In either case, you must report an error.

Each of the nine lines of input contains exactly nine characters that represent the sudoku puzzle. Every character is a digit from 1 to 9 or a period ('.'), which marks an empty cell.

If the initial board is illegal or you hit a contradiction while solving, print GRESKA. Otherwise, print the board in the same format as the input, with every cell filled in whose value can be determined by repeating cross-hatching.