[AdditionalFile163.zip](file://AdditionalFile163.zip?type=additional_file)

#163. 高斯消元 2

题目描述

这可能也是一道模板题。

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

输入格式

第一行一个正整数 $n$，表示矩阵大小。

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

输出格式

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

样例

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

1 2 3

数据范围与提示

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