Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.
Problem hidden on 2012-05-14 10:50:42 by :D

MAGICSQU - Magic Square!

Given an nxn matrix, if it satisfy the next constraints it could be called a "Magic Square".

Constraints:

* The sum of the n rows, n columns and the two main diagonals of the matrix must be equal to the same number m, called magic constant
* the n2 positions of the matrix must contains natural numbers between 1 to n2, with no repetitions.

 

Input

Each test case consist in a natural number n (0 < n <= 20) denoting the matrix dimension. Then, the next n2 natural numbers will represent the values that initially contains the matrix.
For each position aij (1 <= i,j <= n) of the matrix, we have:  0 <= aij <= n2, for all ij.
A value of 0 in an initial position aij of the matrix means that you must find a number to complete that place. A non-zero value means that you cannot change that value for the given position.

Output

For each case you must print the case number (starting from 1).
Then, in the next n lines you must print the magic square if exists or the phrase ''No Solution'' (without the quotes) if doesn't exist a solution for the given initial configuration.

See the output example.

If for a given initial configuration exists more than one solution, you should give the lower one assuming a lexicographic order. For lexicographic comparison you should consider lines in first place.

Print a blank line between test cases.

For example:
2 7 6    
9 5 1    
4 3 8    

it's lexicographically before than:

4 3 8
9 5 1
2 7 6

 

Example

Input:
3
8 0 0
0 0 0
0 0 0

2
1 1
0 0



Output:

Case #1
8 1 6
3 5 7
4 9 2

Case #2
No Solution


Added by:Coach UTN FRSF
Date:2011-06-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2011-06-18 16:21:06 Chetan Gupta
for input:
3
4 0 0
0 0 0
0 0 0

what should be the output??
a)
4 3 8
9 5 1
2 7 6

or

b)
4 9 2
3 5 7
8 1 6
2011-06-18 16:21:06 Coach UTN FRSF
@blashyrkh Your solution is quite good but, like you said, some of your answers are not lexicographically sorted
2011-06-18 16:21:06 blashyrkh
@Coach UTN FRSF: What's wrong with my program #5258894? Some of my answers are not lexicographically lowest or there is something more seriuos?
2011-06-18 16:21:06 Coach UTN FRSF
@Krzysztof Lewko: Why is that weird? there are numbers that are less than 2!!!

@[Trichromatic] XilinX There's no upper bound. Not all test cases have an initial configuration completly empty :)
2011-06-18 16:21:06 Coach UTN FRSF
@blashyrkh thanks, it was fixed!
Yes, input finish with EOF

Last edit: 2011-06-17 12:20:08
2011-06-18 16:21:06 blashyrkh
"No Solution" or "no solution"? Is blank line after the last test case's output needed? Input ends at EOF?

Last edit: 2011-06-17 10:54:26
2011-06-18 16:21:06 :D
It could be that there are more test sets and your program fails on the first with N<=2 (just guessing).
2011-06-18 16:21:06 Krzysztof Lewko
Weird, for assert(n<=2) it gives WA...
2011-06-18 16:21:06 [Rampage] Blue.Mary
What's the upper bound of n?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.