Notes (Important)

The execution time limit for this problem is 2 seconds, but please note that it may vary by about 0.1 seconds depending on the condition of the judge.
Also, if your execution time is very close to the limit, a display such as TLE 47/50 may appear partway through depending on the condition of the judge, but if your execution time is roughly 1.85 seconds or less, it will change to AC upon rejudging.

Unlike a usual AHC, the duration of this contest is "3 hours". Please do not be mistaken about this.

Problem Statement

Everyone, do you know about addition pyramids?
An addition pyramid is a puzzle in which, as shown in the figure below, you first write numbers on the bottom row, and then on each upper row you write the sum of the two numbers below.

In this problem, we consider performing the addition pyramid $\mathrm{mod} \ 10^8$.
That is, only integers between $0$ and less than $10^8$ are written on the bottom row, and if a number exceeds $10^8$ during the calculation, the remainder when divided by $10^8$ is taken.

For each $(i, j)$ $(1 \leq j \leq i \leq N)$, you want to write numbers on the bottom row so that the number in the $i$-th row from the top and the $j$-th column from the left becomes $a_{i,j}$.
However, this may be impossible.

Therefore, write numbers on the bottom row so that the error at the cell with the largest error is as small as possible.
Here, the error between integers $a$ and $b$ is calculated by the following method, which differs from the usual one.

• The smaller of $|a-b|$ and $10^8-|a-b|$ (in particular, the error between $0$ and $99999999$ is $1$)

Score

Let $b_{i,j}$ be the value written in cell $(i, j)$ after the calculation of the addition pyramid is finished. Also, let $e_{i,j}$ be the error between $a_{i,j}$ and $b_{i,j}$, and let $X$ be its maximum value.
Then, your score is $5 \times 10^7-X$ points. *As stated in the problem statement, note that the method of calculating the error differs from the usual one.

There are 50 test cases in total, and the sum of the scores over the test cases is the score of the submission.
However, if an invalid output or a time limit exceeded occurs in one or more test cases, the verdict of the entire submission will be WA or TLE.

Each participant's score can be viewed from the "スコア順" (score order) tab of the problem.

Input

$N$
$a_{1,1}$ 
$a_{2,1}$ $a_{2,2}$
$\vdots$
$a_{N,1}$ $a_{N,2}$ $\cdots$ $a_{N,N}$

The input satisfies the following constraints.

• $N = 50$
• $0 \leq a_{i,j} < 10^8$ $(1 \leq j \leq i \leq N)$
• All input values are integers

Output

Let $c_i$ be the number written $i$-th from the left on the bottom row. Output in the following format.

$c_1$ $c_2$ $\cdots$ $c_N$

(Added at 20:51) Outputs with fewer than $N$ values were previously judged as AC (with the remaining values treated as 0), but the judge has been fixed so that they are judged as WA.

Input Generation

The input is generated by the following method.

• $a_{i, j}$ is chosen uniformly at random from the integers between $0$ and less than $10^8$.

Tools

100 sample inputs, the input generation code, a local tester (C++ / Python), and sample code (C++ / Python) are available at the following URL.

• https://drive.google.com/file/d/1Cmrn7A2g63RuiAylQA8Sm7CJTQyhCGju/view?usp=sharing