【模板】类欧几里得算法

给定 $n,\,a,\,b,\,c$ ，分别求 $\sum\limits_{i=0}^{n}\lfloor \frac{ai+b}{c} \rfloor\,,\ \sum\limits_{i=0}^{n}{\lfloor \frac{ai+b}{c} \rfloor}^2\,,\ \sum\limits_{i=0}^{n}i\lfloor \frac{ai+b}{c} \rfloor$ ，答案对 $998244353$ 取模。多组数据。

第一行给出数据组数 $t$ 。 接下来 $t$ 行，每行有四个整数，分别为每组数据的 $n,\ a,\ b,\ c$ 。

对于每组数据，输出一行三个整数，为三个答案对 $998244353$ 取模的结果。

2
2 1 0 2
4 3 9 6

1 1 2
11 27 27

本题采用 $\mathrm{Special}\ \mathrm{Judge}$。 答对所有第一问可以获得测试点 $40\%$ 的分数，答对所有第二问、第三问可以分别获得另外 $30\%$ 的分数。 |测试点编号|特殊性质| |:-:|:-:| |$1$|$n,\,a,\,b,\,c\leqslant10$| |$2 \sim 3$|$n,\,a,\,b,\,c\leqslant1000$| |$4$|$n,\,a,\,b,\,c\leqslant10^6$| |$5$|$t=1$| |$6 \sim 10$|无| 对于所有测试点，有 $1 \leqslant t \leqslant 10^5,\ 0 \leqslant n,\,a,\,b,\,c \leqslant 10^9,\ c \neq 0$ 。