测试数据来自 system/1027

Limitation

给你一个次数为 \(n\) 且 \(n\) 次项系数为 \(1\) 的多项式 \(M(x)\) 和一个不超过 \(n-1\) 次的多项式 \(P(x)\)，求一个不超过 \(n-1\) 次的多项式 \(Q(x)\)，满足 \(P(x)Q(x) \equiv 1 \pmod {M(x)}\)。

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

其中系数在 \(\mathbb{F}_p\) 下进行，其中 \(p=998244353\)。

Format

Input

第一行输入一个整数 \(n\)，表示多项式的次数。

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

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

Output

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

Sample 1

Input

5
4 1 5 4 1 1
1 9 8 1 0

Output

287603356 114420498 32582651 248944523 227744016

Sample 2

Input

5
4 1 5 4 1 1
287603356 114420498 32582651 248944523 227744016

Output

1 9 8 1 0

Limitation

Data

本题共 \(4\) 个子任务，每个子任务分值 \(25\)，第 \(k\) 个子任务满足 \(n=10^{k+1}\)。

Time and Space

6s, 256MB.

Source

loj #172

update by Shuchong