注意 (重要)

本問題の実行時間制限は 2 秒ですが，ジャッジの調子によって 0.1 秒程度ずれることがありますのでご注意ください。
また，実行時間がギリギリの場合，ジャッジの調子によって途中で TLE 47/50 のように表示されることがありますが，実行時間が概ね 1.85 秒以下の場合は再実行により AC に変わります。

本コンテストの制限時間は通常の AHC とは異なり「3 時間」です。お間違えの無いようお願いします。

問題文

皆さん，足し算ピラミッドをご存知でしょうか。
足し算ピラミッドは，下図のようにまず最下段に数を書き，その後上の段に下の 2 つの数の合計を書いていくパズルです。

今回は，足し算ピラミッドを $\mathrm{mod} \ 10^8$ で行うことを考えます。
すなわち，最下段には $0$ 以上 $10^8$ 未満の整数しか書かず，計算の途中で数が $10^8$ を超えた場合，$10^8$ で割ったあまりを取ります。

あなたは，各 $(i, j)$ $(1 \leq j \leq i \leq N)$ について，上から $i$ 段目・左から $j$ 列目の数が $a_{i,j}$ になるように，最下段に数を書き込みたいです。
しかし，もしかしたらこれは不可能かもしれません。

そこで，最も誤差が大きいマスにおける誤差ができるだけ小さくなるように，最下段に数を書き込んでください。
ただし，整数 $a$ と $b$ の誤差は通常とは異なる以下の方法で計算されます。

• $|a-b|$ と $10^8-|a-b|$ の小さい方 (特に $0$ と $99999999$ の誤差は $1$)

得点

足し算ピラミッドの計算を終えた際にマス $(i, j)$ に書かれた値を $b_{i,j}$ とします。また，$a_{i,j}$ と $b_{i,j}$ の誤差を $e_{i,j}$ とし，その最大値を $X$ とします。
このとき，あなたの得点は $5 \times 10^7-X$ 点となります。 ※問題文に書かれている通り、誤差の計算方法が通常とは異なることに注意してください。

合計で 50 個のテストケースがあり，各テストケースの合計が提出の得点となります。
ただし，1 つ以上のテストケースで不正な出力や実行時間制限超過となった場合，提出全体の判定が WA や TLE となります。

各参加者のスコアは，問題の「スコア順」タブから閲覧することができます。

入力

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

入力は以下の制約を満たす。

• $N = 50$
• $0 \leq a_{i,j} < 10^8$ $(1 \leq j \leq i \leq N)$
• 入力される値はすべて整数

出力

最下段の左から $i$ 番目に書く数を $c_i$ とするとき，以下の形式で出力してください。

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

(20:51 追記) 出力が $N$ 個に満たない場合に AC (残りの出力が 0 となる) と判定されていましたが，WA となるようジャッジを修正しました。

入力生成方法

入力は以下の方法で生成されます。

• $a_{i, j}$ は $0$ 以上 $10^8$ 未満の整数の中から一様ランダムに選ばれる。

ツール類

サンプル入力 100 個，入力生成コード，ローカルテスタ (C++ / Python)，サンプルコード (C++ / Python) は以下の URL より閲覧できます。

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