给你一个大小为 $N \times N \times N$ 的三维整数数组 $A$。

初始化以下变量：

integer x = 0;
integer w = 1;
stack s = {};

然后，对于每个 $t = 0, 1, \dots, N - 1$，选择一个满足 $-1 \le y_t < N$ 的整数 $y_t$，并执行以下操作：

如果 $0 \le y_t$，执行以下操作：

w *= A[t][x][y];
s.push(x);
x = y;

上述代码中的 $y$ 表示 $y_t$。

如果 $y_t = -1$，执行以下操作：

assert(!s.empty());
w *= A[t][x][s.top()];
x = (x + s.top()) % N;
s.pop();

如果在执行操作前栈为空，则不能选择 $y_t = -1$。

注意，栈支持以下操作：

• push(x)：向集合中添加一个元素 x。
• pop()：移除最近添加的元素。
• top()：返回最近添加的元素的值。

对于每个 $i = 0, 1, \dots, N - 1$，考虑所有使得 $x$ 的最终值为 $i$ 的可能序列 $y_0, y_1, \dots, y_{N-1}$。计算所有这些序列对应的 $w$ 值之和，并将结果模 998244353 后输出。

输入格式

输入格式如下：

$N$ $A_{0,0,0} \ \dots \ A_{0,0,N-1}$ $\vdots$ $A_{0,N-1,0} \ \dots \ A_{0,N-1,N-1}$ $\vdots$ $A_{N-1,0,0} \ \dots \ A_{N-1,0,N-1}$ $\vdots$ $A_{N-1,N-1,0} \ \dots \ A_{N-1,N-1,N-1}$

$A_{i,j,k}$ 表示 $A[i][j][k]$ 的值。

输出格式

输出 $N$ 行。在第 $i$ 行（$0 \le i < N$）输出 $i$ 对应的答案。

数据范围

• $1 \le N \le 30$
• $0 \le A_{i,j,k} \le 10^9$ （$0 \le i, j, k < N$）
• 所有输入值均为整数。

样例

输入样例 1

2
1 10
100 1000
1 3
9 27

输出样例 1

92
363

输入样例 2

3
2 1 2
1 2 1
1 1 1
2 1 1
2 2 1
2 2 2
2 1 1
1 2 1
1 2 2

输出样例 2

63
68
56

输入样例 3

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出样例 3

120
120
120
120