#53. 多项式多点求值和多点插值

题目类型:传统型 时间限制:2000 ms 空间限制:256 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

这是一道模板题。

有一个 $n\ -\ 1$ 次多项式 $A(x)$,给定这个多项式在 $x_1,\ x_2,\ x_3,\ \dots,\ x_n$ 处的值 $y_1,\ y_2,\ y_3,\ \dots,\ y_n$ ,你要求出它在 $z_1,\ z_2,\ z_3,\ \dots,\ z_m$ 处的值。


输入格式

一行一个整数 $n$ ,含义如题目描述。

接下来 $n$ 行,每行两个整数 $x_i,\ y_i$。

接下来一行一个整数 $m$,含义如题目描述。

接下来一行 $m$ 个整数,$z_1,\ z_2,\ z_3,\ \dots,\ z_m$。

输出格式

一行 $m$ 个整数,表示函数在 $z_i$ 处的值。


样例一

Input

4
1 1
2 5
3 14
4 30
4
5 6 7 8

Output

55 91 140 204

Explanation

这个多项式就是 $f(x)\ =\ \frac{x\cdot(x\ +\ 1)\cdot(2x\ +\ 1)}{6}$


限制与约定

对于 $100\%$ 的数据,满足 $1\ \leq\ n,\ m\ \leq\ 50000$,保证输入中的系数大于等于 $0$ 且小于 $998244353$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$