Problem Statement

You are given a positive integer $N$. Here, $N$ is one of $2,4,8,16$.

A boxing tournament will be held with $N$ participants numbered $1,2,\dots ,N$. The tournament proceeds as follows.

• Arrange the $N$ participants in a row in some order.
• Each participant at an odd position from the left has exactly $1$ boxing match against the participant immediately to their right; the winner stays in the row and the loser is eliminated from the row. This is repeated until $1$ person remains in the row.
• The $1$ person who remains last is the champion, and the tournament ends.

Noya investigated how each participant matches up against each other participant and created a table $S$ with $N$ rows and $N$ columns. This table represents the following.

For any $i,j\ (1\le i\lt j\le N)$, if $S_{i,\ j}=1$ then participant $i$ always beats participant $j$, and if $S_{i,\ j}=0$ then participant $i$ always loses to participant $j$.

Here, for $1\le i,\ j\le N$, it is guaranteed that $S_{i,\ j} + S_{j,\ i}=1$ if $i\neq j$, and $S_{i,\ j}=0$ if $i=j$.

There are $N!$ ways to arrange the $N$ participants in a row. Among them, how many ways result in participant $k$ becoming the champion?

Output the answer for each of $k=1,2,\dots ,N$.

Constraints

Input

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

Output

Output $N$ lines. On the $i$-th line, output the answer for $k=i$.

Sample

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