【模板】多项式快速插值

题目背景

模板题,无背景

题目描述

给出 $n$ 个点 $(x_i, y_i)$ 求一个 $x-1$ 次的多项式 $f(x)$,使得 $f(x_i)\equiv y_i\pmod{998244353}$

输入输出格式

输入格式


第一行输入一个正整数 $n$ 接下来 $n$ 行每行两个整数 $x_i, y_i$

输出格式


共一行,从低到高输出 $f(x)$ 每一项的系数 若次数不够 $n-1$ 次,用 $0$ 补足

输入输出样例

输入样例 #1

4
1 1
2 4
3 9
4 16

输出样例 #1

0 0 1 0

说明

$1 \leqslant n \leqslant 100000$ $0 \leqslant x_i, y_i \lt 998244353$ 保证 $x_i$ 互不相同 对于 $30\%$ 的数据,$n \leqslant 5000$ 注意,你输出的数必须是 $[0, 998244353)$ 范围内的整数 数据使用 CYaRon 在五分钟之内生成。