$n$개의 검은색 노드와 $n$개의 흰색 노드로 이루어진 그래프 $G$가 주어지며, 모든 간선은 검은색 노드와 흰색 노드만을 연결합니다(즉, 그래프는 이분 그래프입니다).

$G$의 각 간선은 파란색 또는 빨간색 중 하나의 색상을 가집니다. 같은 색상의 두 간선이 동일한 두 정점을 연결할 수 없습니다(즉, 같은 색상의 평행 간선은 존재하지 않습니다).

$0$부터 $n$까지의 모든 $k$에 대하여, $G$에서 정확히 $k$개의 빨간색 간선과 $n-k$개의 파란색 간선을 포함하는 완전 매칭의 개수를 구하십시오. 완전 매칭이란 어떠한 두 간선도 공통 끝점을 공유하지 않는 $n$개 간선의 부분집합임을 상기하십시오. 결과값이 매우 클 수 있으므로, 답을 2로 나눈 나머지만 출력하면 됩니다.

입력

첫 번째 줄에는 음이 아닌 정수 $n$ ($1 \le n \le 300$)이 주어집니다.

다음 $n$개의 줄에는 공백 없이 $n$개의 문자가 주어집니다. 이 줄들은 빨간색 간선의 인접 행렬을 나타냅니다. $i$번째 줄의 $j$번째 문자가 "1"이면 $i$번째 검은색 노드와 $j$번째 흰색 노드를 연결하는 빨간색 간선이 존재함을 의미하고, "0"이면 존재하지 않음을 의미합니다.

그다음 $n$개의 줄은 위와 같은 형식으로 파란색 간선의 인접 행렬을 나타냅니다.

출력

$k = 0, 1, 2, \dots, n$에 대한 답을 각각 $n+1$개의 줄에 출력하십시오. 답은 2로 나눈 나머지만 출력해야 함을 기억하십시오.

예제

입력 1

2
11
10
00
11

출력 1

0
0
1

참고

예제에는 세 개의 완전 매칭이 존재합니다:

1. 빨간색 (1, 1), 파란색 (2, 2) (빨간색 1개, 파란색 1개)
2. 빨간색 (1, 2), 파란색 (2, 1) (빨간색 1개, 파란색 1개)
3. 빨간색 (1, 2), 빨간색 (2, 1) (빨간색 2개, 파란색 0개)

이 매칭들을 통해 $k=0$일 때 0개, $k=1$일 때 0개, $k=2$일 때 1개의 완전 매칭이 존재함을 알 수 있습니다.