注意

この問題の実行時間制限は $10$ 秒です.

問題文

整数 $n,m$ が与えられます. ここで $n\ge 3$ が制約から保証されます.

形式的羃級数 $f(x)\coloneqq \sum_{i=0}^{n-1}a_i x^i\in \mathbb{F}_{998244353}[[x]], g(x)\coloneqq \sum_{i=0}^{n-1}b_i x^i \in\mathbb{F}_{998244353}[[x]], h(x)\coloneqq \sum_{i=0}^{n-1}c_i x^i \in\mathbb{F}_{998244353}[[x]]$ が与えられます. これらは以下の性質を満たすことが制約から保証されます.

• $a_0=0$
• $a_1^i \not\equiv a_1 \pmod {998244353}\ (i=2,3,\dots, n-1)$
• $b_0=0$
• $b_1=1$
• $g(f(x)) \equiv a_1 g(x)\pmod {x^{n}}$
• $g(h(x)) \equiv h(g(x)) \equiv x\pmod {x^{n}}$

$f^{\langle m\rangle}(x)\bmod x^n = \sum_{i=0}^{n-1}\mathrm{ans}_i x^i$ を求めてください. ここで $f^{\langle m\rangle}(x)$ は $f(x)$ の $m$ 回合成を表します.

制約

• 入力はすべて整数
• $3\le n\le 200000$
• $1\le m\le 10^9$
• $0\le a_i,b_i,c_i\lt 998244353$
• $a_0=0$
• $a_1^i \not\equiv a_1 \pmod {998244353}\ (i=2,3,\dots, n-1)$
• $b_0=0$
• $b_1=1$
• 問題文で定義された $f(x),g(x)$ は $g(f(x)) \equiv a_1 g(x)\pmod {x^{n}}$ を満たす
• 問題文で定義された $g(x),h(x)$ は $g(h(x)) \equiv h(g(x)) \equiv x\pmod {x^{n}}$ を満たす

入力

$n$ $m$
$a_0$ $a_1$ $\dots$ $a_{n-1}$
$b_0$ $b_1$ $\dots$ $b_{n-1}$
$c_0$ $c_1$ $\dots$ $c_{n-1}$

出力

次の形式で出力してください. ただし，$\mathrm{ans}_i$ は $0\le \mathrm{ans}_i\lt 998244353$ を満たす整数とします.

$\mathrm{ans}_0$ $\mathrm{ans}_1$ $\dots$ $\mathrm{ans}_{n-1}$

サンプル

4 2
0 2 0 1
0 1 0 831870294
0 1 0 166374059

0 4 0 10

10 1000000000
0 2 97460621 111410723 910781021 787650035 525397272 778634186 769261814 17908181
0 1 450391866 851628676 116766808 102424189 629373870 830133384 438172635 610210161
0 1 547852487 703228107 427427877 24030916 160333921 387872980 756810038 143082494

0 851104391 401777859 691006525 444992555 559055363 329863477 85844850 547301501 52035613