#4669. 模板. 多项式欧几里得

模板. 多项式欧几里得

Description

这是一道模板题。

给你一个次数为 nnnn 次项系数为 11 的多项式 M(x)M(x) 和一个不超过 n1n-1 次的多项式 P(x)P(x),求一个不超过 n1n-1 次的多项式 Q(x)Q(x),满足 P(x)Q(x)1(modM(x))P(x)Q(x) \equiv 1 \pmod {M(x)}

保证 M(x)M(x)P(x)P(x) 没有公因式。

其中系数在 Fp\mathbb F_p 下进行,其中 p=998244353p = 998244353

Input

第一行输入一个整数 nn,表示多项式的次数。

接下来一行输入 n+1n+1 个整数,从低到高次表示 M(x)M(x) 的各项系数,保证最后一个数为 11

接下来一行输入 nn 个整数,从低到高次表示 P(x)P(x) 的各项系数。

Output

输出一行 nn 个整数,从低到高次表示 Q(x)Q(x) 的各项系数。

Samples

5
4 1 5 4 1 1
1 9 8 1 0
287603356 114420498 32582651 248944523 227744016
5
4 1 5 4 1 1
287603356 114420498 32582651 248944523 227744016
1 9 8 1 0

Limitation

本题共 44 个子任务,每个子任务分值 2525,第 kk 个子任务满足 n10k+1n \leq 10^{k+1}