Description

这可能也是一道模板题。

给定稀疏矩阵 $A$，以及列向量 $b$， 其中 $A$ 的非零元素个数不超过 $20000$，求列向量 $x$ 满足 $Ax = b$，对 $998244353$ 取模。

Input

第一行一个正整数 $n$，表示矩阵大小。 接下来 $n$ 行，每行 $n + 1$ 个整数，其中第 $i$ 行前 $n$个整数第 $j$ 个整数表示矩阵 $A_{i, j}$ 的值，最后一个整数表示 $b_i$ 的值。

Output

一行输出 $n$ 个整数并对 $998244353$ 取模。

Samples

3
1 2 0 5
0 1 4 14
2 0 1 5

1 2 3

Limitation

$n \leq 2500$, $0 \leq A_{i, j}, b_i< 998244353$，其中 $A$ 中非零元素个数 $\leq 20000$，且 $\operatorname {rank} A = n$ 。