Bạn được cho một đồ thị $G$ với $n$ đỉnh đen và $n$ đỉnh trắng, trong đó mỗi cạnh chỉ có thể nối một đỉnh đen và một đỉnh trắng (nói cách khác, đồ thị là đồ thị hai phía).

Mỗi cạnh trong $G$ có một màu: xanh hoặc đỏ. Không có hai cạnh nào cùng màu nối cùng một cặp đỉnh (nói cách khác, không có các cạnh song song cùng màu).

Với mỗi $k$ từ $0$ đến $n$, hãy đếm số lượng bộ ghép hoàn hảo trong $G$ chứa chính xác $k$ cạnh đỏ và $n - k$ cạnh xanh. Nhắc lại rằng bộ ghép hoàn hảo là một tập hợp gồm $n$ cạnh mà không có hai cạnh nào chia sẻ chung một đỉnh đầu mút. Vì số lượng có thể rất lớn, bạn chỉ cần xuất kết quả theo modulo 2.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên không âm $n$ ($1 \le n \le 300$).

Mỗi dòng trong $n$ dòng tiếp theo chứa $n$ ký tự không có khoảng trắng. Các dòng này mô tả ma trận kề của các cạnh đỏ. Ký tự thứ $j$ trên dòng thứ $i$ là "1" nếu có một cạnh đỏ nối đỉnh đen thứ $i$ và đỉnh trắng thứ $j$, và là "0" trong trường hợp ngược lại.

$n$ dòng tiếp theo mô tả ma trận kề của các cạnh xanh, theo cùng định dạng như trên.

Dữ liệu ra

Xuất ra $n + 1$ dòng chứa các câu trả lời của bạn tương ứng cho $k = 0, 1, 2, \dots, n$. Hãy nhớ rằng bạn chỉ cần xuất kết quả theo modulo 2.

Ví dụ

Dữ liệu vào 1

2
11
10
00
11

Dữ liệu ra 1

0
0
1

Ghi chú

Trong ví dụ trên, tồn tại ba bộ ghép hoàn hảo:

1. đỏ (1, 1), xanh (2, 2)
2. đỏ (1, 2), xanh (2, 1)
3. đỏ (1, 2), đỏ (2, 1)