AT_abc310_g [ABC310G] Takahashi And Pass-The-Ball Game

[problemUrl]: https://atcoder.jp/contests/abc310/tasks/abc310_g 高橋くんが $ N $ 人います。 $ i $ 番目の高橋くんは、整数 $ A\ _\ i $ とボール $ B\ _\ i $ 個を持っています。 高橋くんたちは $ 1 $ 以上 $ K $ 以下の整数 $ x $ を一様ランダムに選び、次の操作を $ x $ 回繰り返します。 - すべての $ i $ について、$ i $ 番目の高橋くんは $ A\ _\ i $ 番目の高橋くんに自分が持っているボールをすべて渡す。 操作は $ N $ 人によって同時に行われることに注意してください。 $ i=1,2,\ldots,N $ について、一連の操作が終了したとき $ i $ 番目の高橋くんが持っているボールの個数の期待値を $ {}\bmod{998244353} $ で求めてください。 期待値 $ {}\bmod{998244353} $ の定義 この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 $ \frac\ yx $ で表したときに $ x $ が $ 998244353 $ で割り切れないことが保証されます。 このとき、$ y\equiv\ xz\pmod{998244353} $ を満たす $ 0\leq\ z\lt998244353 $ がただ一つ存在するので、$ z $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A\ _\ 1 $ $ A\ _\ 2 $ $ \cdots $ $ A\ _\ N $ $ B\ _\ 1 $ $ B\ _\ 2 $ $ \cdots $ $ B\ _\ N $

$ i=1,2,\ldots,N $ について、操作が終了したとき $ i $ 番目の高橋くんが持っているボールの個数の期待値を空白区切りで $ 1 $ 行に出力せよ。

### 制約 - $ 1\leq\ N\leq\ 2\times10^5 $ - $ 1\leq\ K\leq\ 10^{18} $ - $ K $ は $ 998244353 $ の倍数でない - $ 1\leq\ A\ _\ i\leq\ N\ (1\leq\ i\leq\ N) $ - $ 0\leq\ B\ _\ i\lt998244353\ (1\leq\ i\leq\ N) $ - 入力はすべて整数 ### Sample Explanation 1 操作を $ 2 $ 回行うと、それぞれの高橋くんが持っているボールは以下のようになります。 !\[\](https://img.atcoder.jp/abc310/eeca44e66744660173a72967840e158a.png) $ x=1 $ が選ばれた場合、それぞれの高橋くんが持っているボールの数は $ 4,0,1,2,5 $ 個です。 $ x=2 $ が選ばれた場合、それぞれの高橋くんが持っているボールの数は $ 2,0,4,1,5 $ 個です。 よって、求める期待値はそれぞれ $ 3,0,\dfrac52,\dfrac32,5 $ です。 $ {}\bmod{998244353} $ での値を求めるとそれぞれ $ 3,0,499122179,499122178,5 $ となるので、これらを順に空白区切りで出力してください。 ### Sample Explanation 2 $ 1 $ 回以上操作すると、すべてのボールを $ 1 $ 番目の高橋くんが持つことになります。