TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

Given integer sequences $x_ 0, x_ 1, ..., x_ {N - 1}$ and $y_ 0, y_ 1, ..., y_ {N - 1}$.

Calculate a polynomial $f(x) = \sum_ {i = 0}^ {N - 1} c_ i x^ i \in \mathbb{Z}[x]$ s.t. $f(x_ i) \equiv y_ i (\bmod 998244353)$ is satisfied for each $i$.

Also, $0 \leq c_ i < 998244353$ must be satisfied.

Input Format

$N$
$x_ 0$ $x_ 1$ ... $x_ {N-1}$
$y_ 0$ $y_ 1$ ... $y_ {N-1}$

Output Format

$c_ 0$ $c_ 1$ ... $c_ {N -1}$

Sample Input 1

5
5 6 7 8 9
586 985 1534 2257 3178

Sample Output 1

1 2 3 4 0

Sample Input 2

1
10000000
10000000

Sample Output 2

10000000

Hints

  • $1 \leq N \leq 2^ {17}(=131072)$
  • $0 \leq x_ i, y_ i < 998244353$
  • $x_ i \neq x_ j (i \neq j)$

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 2097152 2097152
1 10000 2097152 2097152
2 10000 2097152 2097152
3 10000 2097152 2097152
4 10000 2097152 2097152
5 10000 2097152 2097152
6 10000 2097152 2097152
7 10000 2097152 2097152
8 10000 2097152 2097152