Hard Linear Algebra Problem

The affinity of two invertible $n \times n$ matrices $A$ and $B$ over $Z_{998244353}$ is the number of indices $i$ ($1 \le i \le n$) that satisfy the following condition.

• If the $i$-th column of $A$ and the $i$-th column of $B$ are swapped, both $A$ and $B$ are still invertible.

In other words, the affinity is an integer from $0$ to $n$.

Define the matrix $A_i$ as the matrix obtained from $A_{i-1}$ by moving its leftmost column to the rightmost position. $A_0 = A$.

For each integer $i$ with $0 \le i < N$, find the affinity of $A_i$ and $B$.

The first line contains a positive integer $n$.

From the second line, the next $n$ lines give the matrix $A$. Each line contains $n$ integers separated by spaces, and the $j$-th integer on the $(i+1)$-th line is $A_{ij}$.

From line $n+2$, the next $n$ lines give the matrix $B$. Each line contains $n$ integers separated by spaces, and the $j$-th integer on the $(i+n+1)$-th line is $B_{ij}$.

Print $n$ integers on the first line, separated by spaces. The $(i+1)$-th integer is the affinity of $A_i$ and $B$.

• $2 \le n \le 200$
• Each entry of the matrices is an integer from $0$ to $998244352$.
• $A$ and $B$ are invertible.