给定一个包含 $n$ 个黑点和 $n$ 个白点的图 $G$，其中每条边仅连接一个黑点和一个白点（换句话说，该图是二分图）。

图 $G$ 中的每条边都有颜色：蓝色或红色。没有两条相同颜色的边连接同一对顶点（换句话说，不存在同色的平行边）。

对于每个 $k$ 从 $0$ 到 $n$，请计算 $G$ 中包含恰好 $k$ 条红边和 $n - k$ 条蓝边的完美匹配的数量。回想一下，完美匹配是 $n$ 条边的子集，其中任意两条边都没有公共端点。由于数字可能很大，你只需要输出模 $2$ 的结果。

输入格式

第一行包含一个非负整数 $n$ ($1 \le n \le 300$)。

接下来的 $n$ 行，每行包含 $n$ 个字符，中间没有空格。这些行共同描述了红边的邻接矩阵。第 $i$ 行的第 $j$ 个字符如果为 “1”，则表示存在一条连接第 $i$ 个黑点和第 $j$ 个白点的红边，否则为 “0”。

接下来的 $n$ 行以相同的格式描述了蓝边的邻接矩阵。

输出格式

输出 $n + 1$ 行，分别包含你对于 $k = 0, 1, 2, \dots, n$ 的答案。请记住，你只需要输出模 $2$ 的答案。

样例

输入格式 1

2
11
10
00
11

输出格式 1

0
0
1

说明

在样例中，存在三个完美匹配：

1. 红边 (1, 1)，蓝边 (2, 2)
2. 红边 (1, 2)，蓝边 (2, 1)
3. 红边 (1, 2)，红边 (2, 1)