Have you ever heard the game called "suduku"?

Yeah, it's a game played on a 9 x 9 board with number 1 to 9.

But 残念です, the game that we will talk is called "kukuku".

"kukuku" is played on 4 x 4 board with number 1 to 4.

The board is partite by 4 big blocks and each big block is partite by 4 small blocks -- There are totally 16 small blocks.

By the Game Rule, you have to put the number between 1 and 4 in each small block,

you must assume each number appears exactly one time in each of rows,columns and big blocks.

NOW, you have a board that some number is already put on it, please count how many ways to solve it, and output the alphabetically first solution.

Example,

1234

4312

2143

3421

is better than

4321

2134

3412

1243

If you solve this problem, you can say "KUKUKU" and have a nice day!!

There is four rows, and each row has four number,

the numbers means the numbers that are put on the small block already.

If the number is 0, it means the block is empty now, you should put the number on it.

Please count how many ways to solve it, and output the alphabetically first solution like Sample Output.

And if there is no way to solve it, please output the message "I can not solve!!"(no double quotation marks)

1 2 3 4

4 3 1 2

2 1 4 3

3 4 2 0

4 3 1 2

2 1 4 3

3 4 2 0

1234

4312

2143

3421

We have 1 way(s) to solve it!!

4312

2143

3421

We have 1 way(s) to solve it!!

原TIOJ1581

No. | Testdata Range | Score |
---|---|---|

1 | 0 | 10 |

2 | 1 | 10 |

3 | 2 | 10 |

4 | 3 | 10 |

5 | 4 | 10 |

6 | 5 | 10 |

7 | 6 | 10 |

8 | 7 | 10 |

9 | 8 | 10 |

10 | 9 | 10 |