Дан граф $G$ с $n$ черными и $n$ белыми вершинами, где каждое ребро соединяет только черную вершину с белой (иными словами, граф является двудольным).

Каждое ребро в $G$ имеет цвет: синий или красный. Никакие два ребра одного цвета не могут соединять одну и ту же пару вершин (иными словами, нет параллельных ребер одного цвета).

Для каждого $k$ от $0$ до $n$ подсчитайте количество совершенных паросочетаний в $G$, которые содержат ровно $k$ красных ребер и $n - k$ синих ребер. Напомним, что совершенное паросочетание — это подмножество из $n$ ребер, в котором никакие два ребра не имеют общих концов. Поскольку число может быть большим, требуется вывести ответы только по модулю 2.

Входные данные

Первая строка содержит неотрицательное целое число $n$ ($1 \le n \le 300$).

Каждая из следующих $n$ строк содержит $n$ символов без пробелов. Эти строки описывают матрицу смежности красных ребер. $j$-й символ в $i$-й строке равен «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)