Background

This is a template problem, with no background.

Problem Description

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}$.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain two integers $x_i, y_i$.

Output Format

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.

4
1 1
2 4
3 9
4 16

0 0 1 0

Hint

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