传球游戏

题目描述

有 $N$ 个高桥。

第 $i$ 个高桥拥有整数 $A_i$ 和 $B_i$ 个球。

将从 $1$ 到 $K$ 之间均匀随机地选择一个整数 $x$,然后重复执行以下操作 $x$ 次:

对于每个 $i$,第 $i$ 个高桥把他所有的球都给第 $A_i$ 个高桥。

注意,所有 $N$ 个高桥同时执行该操作。

对于每个 $i=1,2,\ldots,N$,求操作结束时第 $i$ 个高桥拥有的球数的期望值,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$

输出格式

在一行中,对于 $i=1,2,\ldots,N$,输出操作结束时第 $i$ 个高桥拥有的球数的期望值,用空格分隔。

样例

5 2
3 1 4 1 5
1 1 2 3 5

3 0 499122179 499122178 5

在两次操作期间,5 个高桥拥有如下数量的球。

如果选择 $x=1$,5 个高桥分别拥有 $4,0,1,2,5$ 个球。

如果选择 $x=2$,5 个高桥分别拥有 $2,0,4,1,5$ 个球。

因此,所求期望值为 $3,0,\dfrac{5}{2},\dfrac{3}{2},5$。 将这些值对 $998244353$ 取模,即 $3,0,499122179,499122178,5$,用空格分隔输出。

3 1000
1 1 1
1 10 100

111 0 0

经过一次或多次操作后,第 1 个高桥获得所有球。

16 1000007
16 12 6 12 1 8 14 14 5 7 6 5 9 6 10 9
719092922 77021920 539975779 254719514 967592487 476893866 368936979 465399362 342544824 540338192 42663741 165480608 616996494 16552706 590788849 221462860

817852305 0 0 0 711863206 253280203 896552049 935714838 409506220 592088114 0 413190742 0 363914270 0 14254803

24 100000000007
19 10 19 15 1 20 13 15 8 23 22 16 19 22 2 20 12 19 17 20 16 8 23 6
944071276 364842194 5376942 671161415 477159272 339665353 176192797 2729865 676292280 249875565 259803120 103398285 466932147 775082441 720192643 535473742 263795756 898670859 476980306 12045411 620291602 593937486 761132791 746546443

918566373 436241503 0 0 0 455245534 0 356196743 0 906000633 0 268983266 21918337 0 733763572 173816039 754920403 0 273067118 205350062 0 566217111 80141532 0

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le K \le 10^{18}$
• $K$ 不是 $998244353$ 的倍数。
• $1 \le A_i \le N\ (1 \le i \le N)$
• $0 \le B_i \lt 998244353\ (1 \le i \le N)$
• 输入中的所有值均为整数。

提示

可以证明所求期望值总是有理数。此外,该问题的约束保证了当所求期望值表示为不可约分数 $\dfrac{y}{x}$ 时,$x$ 不被 $998244353$ 整除。

这里,存在唯一的满足 $0 \le z \lt 998244353$ 的整数 $z$,使得 $y \equiv xz \pmod{998244353}$。输出这个 $z$。