You are given two $n \times n$ matrices $\mathbf{A}$ and $\mathbf{B}$. For each $k = 0, 1, 2, \cdots, n$, you need to calculate $f_k=[z^k] \det (\mathbf A + \mathbf B z) \bmod 998,244,353$.

Input

The first line contains a single integer $n$ ($1 \leq n \leq 500$).

The next $n$ lines describes the matrix $\mathbf{A}$:

• The $i$-th line of these lines contains $n$ integers $\mathbf{A}_{i,1}, \mathbf{A}_{i,2}, \cdots, \mathbf{A}_{i, n}$ ($0 \leq \mathbf{A}_{i,j} < 998,244,353$).

The next $n$ lines describes the matrix $\mathbf{B}$:

• The $i$-th line of these lines contains $n$ integers $\mathbf{B}_{i,1}, \mathbf{B}_{i,2}, \cdots, \mathbf{B}_{i, n}$ ($0 \leq \mathbf{B}_{i,j} < 998,244,353$).

Output

Output a single line contains $n + 1$ integers $f_0, f_1, \cdots, f_n$ - describes $\det (\mathbf A + \mathbf B z) = \sum_{i=0}^n f_i z^i$

Examples

Input 1

2
2 1
0 1
1 3
1 0

Output 1

2 0 998244350

Explanation 1

$\det (\mathbf A + \mathbf Bz) = \det \left|\begin{matrix}2+z&1+3z\\z&1\end{matrix}\right| = -3z^2 + 2$

Input 2

3
998244352 998244351 998244350
3 2 0
2 1 2
0 998244352 0
1 0 1
1 1 2

Output 2

11 9 6 1

Input 3

4
0 0 0 0
0 0 0 1
0 1 0 0
0 0 0 1
0 1 0 0
1 1 1 0
0 0 1 1
0 0 0 0

Output 3

0 0 0 998244352 0

Input 4

8
0 0 0 1 8 5 7 6
2 8 3 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 2 2 2 2 2 2
0 0 3 8 9 5 4 4
7 6 5 4 3 2 1 0
8 6 9 4 1 2 3 4
0 0 0 0 0 0 0 0
0 0 0 0 0 5 5 5
1 2 3 4 5 6 7 8
9 9 9 9 5 5 5 4
3 7 8 5 1 7 0 6
2 4 9 8 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1

Output 4

0 0 998068769 997897737 998126353 79000 3360 0 0

Input / Output 5

You can find them in the additional files.

Scoring

• Subtask 1(30 points): $1 \leq n \leq 50$
• Subtask 2(30 points): $\mathbf B_{i,j} = \begin{cases} 1 & i = j \\ 0 & \mathrm{otherwise}\end{cases}$
• Subtask 3(40 points): No additional constraints.