Problem Statement

There are $N$ Takahashi.

The $i$-th Takahashi has an integer $A_i$ and $B_i$ balls.

An integer $x$ between $1$ and $K$, inclusive, will be chosen uniformly at random, and they will repeat the following operation $x$ times.

• For every $i$, the $i$-th Takahashi gives all his balls to the $A_i$-th Takahashi.

Beware that all $N$ Takahashi simultaneously perform this operation.

For each $i=1,2,\ldots,N$, find the expected value, modulo $998244353$, of the number of balls the $i$-th Takahashi has at the end of the operations.

How to find a expected value modulo $998244353$ It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998244353$. Here, there is a unique $0\leq z\lt998244353$ such that $y\equiv xz\pmod{998244353}$, so report this $z$.

Constraints

• $1\leq N\leq 2\times10^5$
• $1\leq K\leq 10^{18}$
• $K$ is not a multiple of $998244353$.
• $1\leq A _ i\leq N\ (1\leq i\leq N)$
• $0\leq B _ i\lt998244353\ (1\leq i\leq N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A _ 1 A _ 2 \cdots A _ N
B _ 1 B _ 2 \cdots B _ N

Output

Print the expected value of the number of balls the $i$-th Takahashi has at the end of the operations for $i=1,2,\ldots,N$, separated by spaces, in a single line.