Se te da un grafo $G$ con $n$ nodos negros y $n$ nodos blancos, donde cada arista solo puede conectar un nodo negro y un nodo blanco (en otras palabras, el grafo es bipartito).

Cada arista en $G$ tiene un color: azul o rojo. No hay dos aristas del mismo color que puedan conectar el mismo par de vértices (en otras palabras, no hay aristas paralelas del mismo color).

Para cada $k$ desde $0$ hasta $n$, por favor cuenta el número de emparejamientos perfectos en $G$ que contienen exactamente $k$ aristas rojas y $n - k$ aristas azules. Recuerda que un emparejamiento perfecto es un subconjunto de $n$ aristas en el cual no hay dos aristas que compartan un extremo común. Dado que el número puede ser grande, solo se requiere que entregues las respuestas módulo 2.

Entrada

La primera línea contiene un entero no negativo $n$ ($1 \le n \le 300$).

Cada una de las siguientes $n$ líneas contiene $n$ caracteres sin espacios. En conjunto, estas líneas describen la matriz de adyacencia de las aristas rojas. El $j$-ésimo carácter en la $i$-ésima línea es "1" si existe una arista roja que conecta el $i$-ésimo nodo negro y el $j$-ésimo nodo blanco, y "0" en caso contrario.

Las siguientes $n$ líneas describen la matriz de adyacencia de las aristas azules, en el mismo formato que el anterior.

Salida

Imprime $n + 1$ líneas que contengan tus respuestas para $k = 0, 1, 2, \dots, n$ respectivamente. Recuerda que solo necesitas imprimir la respuesta módulo 2.

Ejemplos

Entrada 1

2
11
10
00
11

Salida 1

0
0
1

Nota

En el ejemplo, existen tres emparejamientos perfectos:

1. rojo (1, 1), azul (2, 2)
2. rojo (1, 2), azul (2, 1)
3. rojo (1, 2), rojo (2, 1)