Dany jest graf $G$ z $n$ czarnymi wierzchołkami i $n$ białymi wierzchołkami, w którym każda krawędź łączy wyłącznie czarny wierzchołek z białym (innymi słowy, graf jest dwudzielny).

Każda krawędź w $G$ ma kolor: niebieski lub czerwony. Żadne dwie krawędzie tego samego koloru nie mogą łączyć tej samej pary wierzchołków (innymi słowy, nie ma równoległych krawędzi tego samego koloru).

Dla każdego $k$ od $0$ do $n$, oblicz liczbę skojarzeń doskonałych w $G$, które zawierają dokładnie $k$ czerwonych krawędzi oraz $n - k$ niebieskich krawędzi. Przypomnijmy, że skojarzenie doskonałe to podzbiór $n$ krawędzi, w którym żadne dwie krawędzie nie mają wspólnego wierzchołka. Ponieważ liczba ta może być duża, wymagane jest jedynie podanie odpowiedzi modulo 2.

Wejście

Pierwsza linia zawiera nieujemną liczbę całkowitą $n$ ($1 \le n \le 300$).

Każda z kolejnych $n$ linii zawiera $n$ znaków bez spacji. Linie te opisują macierz sąsiedztwa czerwonych krawędzi. $j$-ty znak w $i$-tej linii jest równy „1”, jeśli istnieje czerwona krawędź łącząca $i$-ty czarny wierzchołek z $j$-tym białym wierzchołkiem, a „0” w przeciwnym przypadku.

Kolejne $n$ linii opisuje macierz sąsiedztwa niebieskich krawędzi w tym samym formacie co powyżej.

Wyjście

Wypisz $n + 1$ linii zawierających odpowiedzi dla $k = 0, 1, 2, \dots, n$. Pamiętaj, że należy wypisać wynik modulo 2.

Przykład

Wejście 1

2
11
10
00
11

Wyjście 1

0
0
1

Uwagi

W przykładzie istnieją trzy skojarzenia doskonałe:

1. czerwona (1, 1), niebieska (2, 2)
2. czerwona (1, 2), niebieska (2, 1)
3. czerwona (1, 2), czerwona (2, 1)