G. Diophantine Equation
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Little A has obtained a Diophantine equation.

Given a sequence of positive integers $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$ and a fixed value $$$t$$$, determine a sequence of non-negative integers $$$x_1, x_2, \cdots, x_n$$$ of length $$$n$$$ such that for all $$$0 \leq j \lt n$$$, the following congruence holds:

$$$$$$ \sum_{i=1}^n a_i^j \times x_i \equiv t^j \pmod{998244353}. $$$$$$

Output the sequence $$$x_1, x_2, \cdots, x_n$$$. Note that for each $$$i = 1, 2, \cdots, n$$$, the value $$$x_i$$$ must satisfy $$$0 \leq x_i \lt 998244353$$$.

The data guarantees that the solution is unique.

Input

The first line contains two positive integers $$$n, t$$$ $$$(1 \leq n \leq 5 \times 10^4, 1 \leq t \lt 998244353)$$$.

The second line contains $$$n$$$ positive integers, representing $$$a_1, a_2, \ldots, a_n$$$ in order $$$(1 \leq a_i \lt 998244353)$$$.

Output

Output one line containing $$$n$$$ non-negative integers representing $$$x_1, x_2, \cdots, x_n$$$. Note that for each $$$i = 1, 2, \cdots, n$$$, the value $$$x_i$$$ must satisfy $$$0 \leq x_i \lt 998244353$$$.

The solution is guaranteed to be unique.

Example
Input
2 3
1 2
Output
998244352 2