Serious businessman Vladimir Bludgeon, who was once well known as Scorched Vlad, controls a trust of N enterprises. A former accomplice of Vladimir, famous banker Alexander Ironfist, whose alias was Wry Alex, owns a holding company of N banks. As it should be among the old friends, the enterprises of Mr. Bludgeon take credits at the banks of Mr. Ironfist only, and the banks of Mr. Ironfist give credits to the enterprises of Mr. Bludgeon only. For the purpose of tax evasion all data about the amounts of the credits was properly hidden till one day...

...When an old rival of Vladimir and Alexander, police general Ivan Crowbar alias Rotten Ivan got in their road. Mr. Crowbar dreamed to make Mr. Bludgeon and Mr. Ironfist pay for old insults. In the course of the brilliant operation (this story is fully described in the problem "Credit operations") he obtained so-called credit matrix. Here the credit matrix is a square table with N rows and N columns, and each element A[i, j] of this matrix is equal to amount of the credit which was taken by i-th enterprise of Mr. Bludgeon at j-th bank of Mr. Ironfist.

Ivan understood the phrase "to pay for old insults" literally, so he did not waste time and passed the credit matrix (for a considerable fee, of course) to his old friend, tax police chief Peter Bullman, who appeared in criminal chronicles as Red Bull Pete. Based on such a strong evincive basis, Mr. Bullman was in his right to make Vladimir and Alexander to serve time in jail till doomsday, but... The years of service at tax policy were not in vain for him, and Peter realized at once that this stuff a great way to apply a system approach and finally get rich - or die trying!

Mr. Bullman's system approach came to a fact that each enterprise of Mr. Bludgeon should pay BR[i] dollars as a bribe, and each bank of Mr. Ironfist should pay BC[j] dollars as a bribe. An amount of each credit stated in the credit matrix should not exceed a sum of bribes of an enterprise which took this credit and a bank which gave it (i.e. the following condition should be satisfied: A[i, j] ≤ BR[i]+BC[j]). At that the bribes should be presented as integer non-negative numbers, because Peter dropped out his studies when he was at elementary school, so he does not know any other kinds of numbers. However, it does not prevent him from being a tax policy chief since most of his subordinates did not go to school at all.

To Mr. Bullman's credit, he displayed a certain gallantry and allowed Vladimir and Alexander to calculate amounts of the bribes, which satisfy these conditions on their own. So during a meeting of the committee of directors, which was held in a bath-house as usual, Mr. Bludgeon and Mr. Ironfist have reasonably resolved to minimize the total amount of all bribes and forced their best programmer Alexander Sergeyev to solve this problem.

The first line contains the integer number N (2 ≤ N ≤ 100). Each of the next N lines contains N integer numbers which are corresponding elements A[i, j] (0 ≤ A[i, j] ≤ 10⁶) of the credit matrix.

The first line should contain the optimal values BR[i] for all enterprises. The second line should contain the optimal values BC[j] for all banks. The values should be separated by single spaces. If the problem has several solutions, you should output any of them.