【模板】多项式优化拉格朗日多点插值多点求值

题号：NC302663
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

本题数据量较大，建议您选取较快的输入输出方式。

在第二场网络赛中，托姆深刻体会到了仅仅掌握常用算法是完全不够的，对于新算法的学习仍然是不可或缺的。特别是对于多项式相关的算法，更需要深入理解其数学原理。

今天虽然是一个娱乐赛，但是在娱乐的同时，也让我们学习新的算法。通过这道题目，托姆希望大家能够掌握相关的算法，为今后的比赛打下坚实的基础。

给定 $n$ 个横坐标不同的点 $(x_i, y_i)$ ，其中 $1 \leq i \leq n$ ，所有坐标都是非负整数。

接下来有 $q$ 次询问，每次询问给出一个横坐标 $x_0$ ，请你找到一个纵坐标 $y_0$ ，使得存在一个最高次不超过 $n$ 次的多项式 $f(x)$ ，满足：

$\hspace{15pt}\bullet\,$ $f(x_i) \equiv y_i \pmod{998244353}$ 对所有 $1 \leq i \leq n$ 成立
$\hspace{15pt}\bullet\,$ $f(x_0)\equiv y_0 \pmod{998244353}$

最高次不超过 $n$ 次的多项式指的是形如 $f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ 的多项式，其中 $a_i$ 是系数（在模 $998244353$ 意义下），且 $0 \leq a_i < 998244353$ 。

例如 $f(x) = 2x^3 + 3x^2 + x + 1$ 是一个最高次不超过 $3$ 次的多项式，因为最高次项为 $x^3$ 。

$f(x) = 0x^3 + 0x^2 + 0x + 9$ 是一个最高次不超过 $3$ 次的多项式，因为最高次项为常数项。

$f(x) = x^{3.5} + 2x^2 + 1$ 不是一个最高次不超过 $3$ 次的多项式，因为 $x$ 的次方不是整数。

$f(x) = x^{4} + 2x + 1$ 不是一个最高次不超过 $3$ 次的多项式，因为 $x$ 最高次项为 $x^4$ 。

输入描述:

第一行包含一个正整数  ，表示点的个数。

接下来  行，每行包含两个非负整数  和  ，表示第  个点的坐标。保证给定的  个点的横坐标  互不相同。

接下来一行包含一个正整数  ，表示询问次数。

接下来  行，每行包含一个非负整数  ，表示询问的横坐标。

输出描述:

对于每个询问，输出一行，包含一个非负整数 ，表示满足条件的纵坐标。若存在多个答案，任意输出一个即可。答案需要对  取模。

示例1

输入

复制

输出

复制

示例2

输入

复制

输出

复制

11
821
7337

说明

存在多项式 ，满足：

- 

- 

- 

- 

- 

- 

-