問題文

正整数 $N$ が与えられます。ただし、$N$ は $2,4,8,16$ のいずれかです。

$1,2,\dots ,N$ の番号がついた $N$ 人の参加者によるボクシングのトーナメント戦をします。 トーナメントは以下の方式で行われます。

• $N$ 人の参加者をある順番で横一列に並べる。
• 左から奇数番目の参加者は右隣の参加者と $1$ 度だけボクシングの試合を行い、勝った人は列に残り負けた人は列から脱落する。 列に残った人が $1$ 人になるまで繰り返す。
• 最後に残った $1$ 人が優勝者となり、トーナメントを終了する。

Noya君は、任意の参加者の他の参加者に対する相性を調べ、$N$ 行 $N$ 列からなる表 $S$ を作成しました。 この表は以下のことを表します。

任意の $i,j\ (1\le i\lt j\le N)$ について、$S_{i,\ j}=1$ のとき参加者 $i$ は参加者 $j$ に必ず勝ち、 $S_{i,\ j}=0$ のとき参加者 $i$ は参加者 $j$ に必ず負ける。

ただし、$1\le i,\ j\le N$ について $i\neq j$ ならば $S_{i,\ j} + S_{j,\ i}=1$ 、$i=j$ ならば $S_{i,\ j}=0$ が保証されます。

$N$ 人の参加者を横一列に並べる方法は $N!$ 通りありますが、このうち参加者 $k$ が優勝者となる方法は何通りありますか。

$k=1,2,\dots ,N$ について答えを出力してください。

制約

入力

$N$
$S_{1,1}$ $S_{1,2}$ $\dots$ $S_{1,N}$
$\vdots$
$S_{N,1}$ $S_{N,2}$ $\dots$ $S_{N,N}$

出力

$N$ 行出力してください。$i$ 行目には $k=i$ のときの答えを出力してください。

サンプル

2
0 1
0 0

2
0

4
0 1 0 1
0 0 1 0
1 0 0 1
0 1 0 0

8
0
16
0

8
0 1 0 1 0 1 0 1
0 0 1 0 1 0 1 0
1 0 0 1 0 1 0 1
0 1 0 0 1 0 1 0
1 0 1 0 0 1 0 1
0 1 0 1 0 0 1 0
1 0 1 0 1 0 0 1
0 1 0 1 0 1 0 0

4480
4352
5888
2944
8320
1664
11648
1024