Modular Polynomial Interpolation

Given n distinct points \((x_i, y_i)\), find a polynomial \(f(x)\) of degree \(n-1\) such that

[ f(x_i) \equiv y_i \pmod{998244353} ]

for \(i = 1, 2, \ldots, n\). The answer should be output as \(n\) space-separated integers representing the coefficients \(f_0, f_1, …, f_{n-1}\) of the polynomial:

[ f(x) = f_0 + f_1x + f_2x^2 + \cdots + f_{n-1}x^{n-1} ]

All arithmetic is performed modulo 998244353.

inputFormat

The first line contains a single integer \(n\) denoting the number of points. Each of the following \(n\) lines contains two integers \(x_i\) and \(y_i\) separated by a space. It is guaranteed that all \(x_i\) are distinct.

outputFormat

Output \(n\) space-separated integers \(f_0, f_1, \ldots, f_{n-1}\), which are the coefficients of the unique polynomial \(f(x)\) of degree \(n-1\) satisfying \(f(x_i) \equiv y_i \pmod{998244353}\) for all \(i\). Each coefficient should be given modulo 998244353.

sample

1
5 7

7