#4662. 模板. 高斯消元 2

模板. 高斯消元 2

Description

可能也是一道模板题。

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

Input

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

Output

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

Samples

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

Limitation

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