P5158 [Template] Fast Polynomial Interpolation

This is a template problem, with no background.

You are given $n$ points $(x_i, y_i)$. Find a polynomial $f(x)$ of degree $n - 1$ such that $f(x_i)\equiv y_i\pmod{998244353}$.

The first line contains a positive integer $n$. The next $n$ lines each contain two integers $x_i, y_i$.

Output one line: the coefficients of $f(x)$ from low degree to high degree. If the degree is less than $n - 1$, pad with $0$ until there are $n$ coefficients.

Constraints: $1 \leqslant n \leqslant 100000$. $0 \leqslant x_i, y_i \lt 998244353$. It is guaranteed that all $x_i$ are pairwise distinct. For $30\%$ of the testdata, $n \leqslant 5000$. Note that the numbers you output must be integers in the range $[0, 998244353)$. The testdata was generated using CYaRon within five minutes. Translated by ChatGPT 5