165 拉格朗日插值

这是一道模板题。

维护一个点集 $S$，初始时点集为空集。下面依次进行 $n$ 个操作，操作有两种：

• 1 x y：向点集中添加点 $(x, y)$。保证点集中 $x$ 互不相同。
• 2 k：输出 $f(k) \bmod 998244353$ 的值，其中 $f(x)$ 是一个次数不超过 $|S| - 1$ 次的函数，且经过 $S$ 中所有的点。

第一行，一个整数 $n$，表示操作个数。

接下来 $n$ 行，每行 $2$ 或 $3$ 个整数，描述操作。

数据保证第一个操作必定为 1 类型操作。

多行，第 $i$ 行，一个整数，表示对第 $i$ 个 2 类型操作要求计算的 $f(k) \bmod 998244353$ 的值。

初始时点集 $S = \emptyset$。

第一个操作 1 2 3，向点集中插入点 $(2, 3)$。此时点集 $S = {(2, 3)}$。

第二个操作 2 5，询问 $f(5)$ 的值。唯一满足次数不超过 $0$ 次且经过点 $(2, 3)$ 的函数为 $f(x) = 3$，因此 $f(5) = 3$。

第三个操作 1 4 5，向点集中插入点 $(4, 7)$。此时点集 $S = {(2, 3), (4, 7)}$。

第四个操作 2 5，询问 $f(5)$ 的值。唯一满足次数不超过 $1$ 次且经过点 $(2, 3), (4, 7)$ 的函数为 $f(x) = 2x - 1$，因此 $f(5) = 9$。

第五个操作 1 1 4，向点集中插入点 $(1, 4)$。此时点集 $S = {(2, 3), (4, 7), (1, 4)}$。

第六个操作 2 5，询问 $f(5)$ 的值。唯一满足次数不超过 $2$ 次且经过点 $(2, 3), (4, 7), (1, 4)$ 的函数为 $f(x) = x^2 - 4x + 7$，因此 $f(5) = 12$。

对于 $100\%$ 的数据，$1 \leq n \leq 3000, 1 \leq x, y, k < 998244353$，所有 $x$ 互不相同。

数据有一定梯度。