$n$ 個の黒いノードと $n$ 個の白いノードを持つグラフ $G$ が与えられます。すべての辺は黒いノードと白いノードのみを接続します（言い換えれば、このグラフは二部グラフです）。

$G$ 内の各辺には青または赤の色がついています。同じ色の辺が同じ頂点のペアを接続することはありません（言い換えれば、同色の平行辺は存在しません）。

$0$ から $n$ までのすべての $k$ について、$G$ における完全マッチングのうち、ちょうど $k$ 本の赤い辺と $n - k$ 本の青い辺を含むものの個数を数えてください。完全マッチングとは、$n$ 本の辺からなる部分集合であり、どの2つの辺も共通の端点を共有しないものであることを思い出してください。答えは非常に大きくなる可能性があるため、答えを $2$ で割った余りを出力するだけで構いません。

入力

1行目には非負整数 $n$ ($1 \le n \le 300$) が含まれます。

続く $n$ 行には、それぞれスペースなしで $n$ 文字が含まれます。これらの行は赤い辺の隣接行列を表します。$i$ 行目の $j$ 番目の文字は、$i$ 番目の黒いノードと $j$ 番目の白いノードを接続する赤い辺が存在する場合は "1"、そうでない場合は "0" です。

続く $n$ 行は、上記と同じ形式で青い辺の隣接行列を表します。

出力

$k = 0, 1, 2, \dots, n$ それぞれに対する答えを、$n + 1$ 行に出力してください。答えは $2$ で割った余りのみを出力すればよいことに注意してください。

入出力例

入力 1

2
11
10
00
11

出力 1

0
0
1

注記

例において、完全マッチングは3つ存在します。

1. 赤 (1, 1), 青 (2, 2)
2. 赤 (1, 2), 青 (2, 1)
3. 赤 (1, 2), 赤 (2, 1)