UCBINTA - Sum

 

Once upon a time, there existed a sequence A consisting of N positive integers. You don't know the

sequence itself, but you do know the sum of every two elements of the sequence. Find the sequence A!

Input

The first line of input contains the positive integer N (2 ≤ N ≤ 1000). Each of the following N lines

contains N positive integers smaller than or equal to 100000, forming the table S. The following relations

hold: S(i, j) = A[i] + A[j] for i ≠ j, and S(i, j) = 0 for i = j. Here S(i, j) denotes the number in the

ith row and jth column of the table, and A[i] denotes the ith element of the sequence A. It is guaranteed

that for any input data set there exists a unique sequence of positive integers A with the given properties.

Output

The first and only line of output must contain the required sequence A (in the form of N space separated

positive integers).

Example

Input:
2
0 2
2 0

Output:
1 1
Input:
4
0 3 6 7
3 0 5 6
6 5 0 9
7 6 9 0

Output:
2 1 4 5

Added by:Gabriel Menacho
Date:2014-09-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2012/2013, round 6, http://www.soj.me/9562

hide comments
2015-07-21 15:56:11 kp
reason to be moved to tutorial??
2015-05-10 17:37:28 ASHUTOSH DWIVEDI
simple maths
2015-03-26 14:50:38 [Mayank Pratap]
Motivating problem for beginners like me :)
2015-03-23 19:59:46 iitramar
for n=2 , will there be more than one possibility??
2015-03-18 17:38:32 ViKku
AC in one go.....very simple
2015-02-11 14:59:34 Gaurav sharma
easy one.......no need of hint :P
2015-01-11 21:03:38 Adrian Satja Kurdija
The source of the problem is COCI 2012/2013, round 6. Please state it!
2015-01-01 00:31:39 Tushar Sinha
easy one, just need to focus on getting only one term !!
2014-12-29 15:20:09 :.Mohib.:
Awsm half century completed..... :)...with this easy one...
2014-12-02 09:58:13 NEXES
AC in one go.........damm easy
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.