PAYBACK - Byteland Money Exchange

In Byteland after the food shortage banks made credit payment freely available. At the end of the year companies have to settle their debts and to give a statement on their cashflow to the Claim Office. Among Banks and Companies a net of debts was created. Unfortunetely Banks gave a sky-high price on money transfers. For company owners it was unprofitable to pay all money transfers as they were. They chose you to help them out. Your assignment is to balance the debt network.

You are given [t<=1000] test cases- a test case consists of the size [N<=1000] of the debt network, followed by a description of the network itself. Each line consists of integers separated by spaces ending with a new line. Each value states how much money the company in line "i" is in debt to company "j" where "j" is the column number.

Your assignment is to limit the number of money transfers by determining which companies are in debt, which have earned money and which have shown neither profit nor loss.

Input

t [- test cases]
N [- size of the debt net]
a[1,1] a[1,2] a[1,3] ... a[1,n]
a[2,1] a[2,2] a[2,3] ... a[2,n]
...[[debt size for each company - a[1,3] denotes the sum borrowed by company 1 from 3]]
...
a[n,1] a[n,2] a[n,3] ... a[n,n]
[empty line]
[next test case]

a graphical example

INPUT Graph

Output

T[Size of solution]
a[1,1] a[1,2] a[1,3] ... a[1,n]
a[2,1] a[2,2] a[2,3] ... a[2,n]
...[[debt size for each company - a[1,3] denotes the sum borrowed by company 1 from 3]]
...
a[n,1] a[n,2] a[n,3] ... a[n,n]
[empty line]
[next solution]

[All the output data should be integers.]
Text grouped in [ ] does not appear in the input file.

a graphical example

OUTPUT Graph1

a graphical example- same input

OUTPUT Graph2

Example

Input:
1
7
0 18 25 34 14 21 40 
44 0 64 0 11 5 24 
11 35 0 23 17 26 23 
19 50 20 0 16 7 0 
0 14 9 0 0 27 18 
42 5 17 8 3 0 17 
36 26 0 47 7 6 0 


Output:
7
0 10 0 0 0 0 0 
0 0 0 0 0 0 0 
0 12 0 0 0 6 3 
0 0 0 0 0 0 59 
0 0 0 0 0 0 29 
0 0 0 0 0 0 0 
0 0 0 0 0 0 0

Added by:Sylwester Herber
Date:2005-12-01
Time limit:3.221s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:inspired by "Algorithm Complexity Theory" project assignment 2002

hide comments
2015-01-11 15:49:50 deepesh17feb
total amount after calculate[cred - debt] comes out to be zero for each,please reply
2013-08-12 08:59:24 Sylwester Herber
@Imre Palik - Would you mind to elaborate?
2009-06-11 16:10:25 Imre Palik
The sample output is wrong.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.