题目描述

这可能也是一道模板题。

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

输入格式

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

输出格式

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

样例

input

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

output

1 2 3

数据范围与提示

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