Sum of a Sequence

Interview

Time limit1sMemory limit256 MB

Summary

Given an N by N table holding Ai+Aj for every pair of distinct indices and 0 on the diagonal, recover the original positive sequence A.

Level: Medium5 of 10
Topics: Math, Array, Implementation, Brute force
Solved: No attempts yet

Problem

There is a sequence of positive integers $A = (A_1, A_2, \dots, A_N)$ of length $N$ . You are given a table $S$ that collects the sum of every pair of distinct elements of the sequence. That is, $S(i, j) = A_i + A_j$ when $i \neq j$ , and $S(i, j) = 0$ when $i = j$ .

Given the table $S$ , write a program that reconstructs the original sequence $A$ .

Input

The first line contains the length of the sequence $N$ . ( $2 \le N \le 1000$ )

Each of the next $N$ lines contains $N$ integers. The $j$ -th integer on the $i$ -th line is $S(i, j)$ , where $S(i, j) = A_i + A_j$ when $i \neq j$ and $S(i, j) = 0$ when $i = j$ . Every element of the sequence is a positive integer not greater than $10^5$ .

The sequence $A$ corresponding to the given table $S$ is always unique.

Output

Print the elements of the sequence $A$ in order on the first line, separated by spaces.

Examples2

Example 1
Input
```
2
0 2
2 0
```
Expected output
```
1 1
```

Example 2

Input

Expected output

2 1 4 5