Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sudoku

By subeen · Limits 2s, 512 MB

The Prothom Alo newspaper sometimes publishes Sudoku for interested readers to solve. Later the solutions are also published. One day, Prothom Alo Editor Matiur Rahman thought, as everything is becoming digital, there should also be a digital version of Sudoku. Then readers will be able to submit the solution on the newspaper website. He assigned Munir Hasan for that job. Now Munir Hasan is a very busy person, he cannot possibly manage to do it himself. Besides, he have been away from programming for a long while. So he appointed a web developer for the task. Within a month the web developer implemented the system. But he was unable to write the program to check whether the Sudoku solution was correct. While being charged by Munir Hasan about that matter, he said, “Sir, I don’t know any logic”. Anyway, now your task is to rescue Munir Hasan from this situation.

A Sudoku consists of a 9×99 \times 9 board (with a total of 8181 cells). Initially some cells are filled with a number between 11 and 99. The remaining empty cells are to be filled with numbers ranging from 11 to 99. This should be done in such a way that, no row have the same number more than once and no column have the same number more than once. Each of the nine squares of size 3×33 \times 3 in that 9×99 \times 9 board can also have any number from 11 to 99 only once.

Input

A 9×99 \times 9 Sudoku board where each cell is filled with a number between 11 to 99.

Output

Print Congratulations! If the Sudoku solution is correct. Otherwise print Oh No!

Sample

InputOutput
987265341
987654321
123456789
214365879
896745231
132457689
214365879
112233449
887788776
Oh No!

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.