Vous disposez d'un graphe $G$ avec $n$ nœuds noirs et $n$ nœuds blancs, où chaque arête ne peut relier qu'un nœud noir et un nœud blanc (en d'autres termes, le graphe est biparti).

Chaque arête dans $G$ possède une couleur : soit bleue, soit rouge. Deux arêtes de la même couleur ne peuvent pas relier la même paire de sommets (en d'autres termes, il n'y a pas d'arêtes parallèles de même couleur).

Pour chaque $k$ de $0$ à $n$, veuillez compter le nombre de couplages parfaits dans $G$ qui contiennent exactement $k$ arêtes rouges et $n - k$ arêtes bleues. Rappelons qu'un couplage parfait est un sous-ensemble de $n$ arêtes dans lequel aucune paire d'arêtes ne partage une extrémité commune. Comme le nombre peut être grand, vous n'êtes tenu de fournir que les réponses modulo 2.

Entrée

La première ligne contient un entier non négatif $n$ ($1 \le n \le 300$).

Chacune des $n$ lignes suivantes contient $n$ caractères sans espaces. Ensemble, ces lignes décrivent la matrice d'adjacence des arêtes rouges. Le $j$-ième caractère sur la $i$-ième ligne est « 1 » s'il existe une arête rouge reliant le $i$-ième nœud noir et le $j$-ième nœud blanc, et « 0 » sinon.

Les $n$ lignes suivantes décrivent la matrice d'adjacence des arêtes bleues, dans le même format que ci-dessus.

Sortie

Affichez $n + 1$ lignes contenant vos réponses pour $k = 0, 1, 2, \dots, n$ respectivement. N'oubliez pas que vous n'avez besoin d'afficher la réponse que modulo 2.

Exemples

Entrée 1

2
11
10
00
11

Sortie 1

0
0
1

Remarque

Dans l'exemple, il existe trois couplages parfaits :

1. rouge (1, 1), bleu (2, 2)
2. rouge (1, 2), bleu (2, 1)
3. rouge (1, 2), rouge (2, 1)