简单版本和困难版本之间的唯一区别是限制。
Nauuo是一个喜欢随机图片网站的女孩。
有一天,她自己制作了一个随机图片网站,其中包含$$$n$$$图片。
当 Nauuo 访问该网站时,她只看到一张图片。该网站不会以相同的概率显示每张图片。第$$$i$$$张图片的权重为非负$$$w_i$$$,第$$$i$$$张图片被显示的概率为$$$\frac{w_i}{\sum_{j=1}^nw_j}$$$。也就是说,一张图片被展示的概率与其权重成正比。
然而,Nauuo 发现一些她不喜欢的图片显示得太频繁。
为了解决这个问题,她想出了一个好主意:当她看到一张自己喜欢的图片时,她会在它的权重上加上$$$1$$$;否则,她会从它的重量中减去$$$1$$$。
Nauuo 将访问该网站 $$$m$$$ 次。她想知道在所有 $$$m$$$ 访问模 $$$998244353$$$ 后每张图片的预期权重。你能帮助她吗?
第$$$i$$$张图片的预期权重可以用$$$\frac {q_i} {p_i}$$$表示,其中$$$\gcd(p_i,q_i)=1$$$,你需要打印一个整数$$$r_i$$$,满足$$$0\le r_i<998244353$$$并且$$$r_i\cdot p_i\equiv q_i\pmod{998244353}$$$。可以证明这样的$$$r_i$$$存在并且是唯一的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n\le 50$$$, $$$1\le m\le 50$$$) — 图片数量和网站访问次数。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i$$$ 是 $$$0$$$ 或 $$$1$$$) — 如果 $$$a_i=0$$$ ,Nauuo 不喜欢第 $$$i$$$ 图片;否则 Nauuo 喜欢第 $$$i$$$ 张图片。保证至少有一张Nauuo喜欢的图片。
第三行包含 $$$n$$$ 整数 $$$w_1,w_2,\ldots,w_n$$$ ($$$1\le w_i\le50$$$) — 图片的初始权重。
输出
输出包含 $$$n$$$ 整数 $$$r_1,r_2,\ldots,r_n$$$ — 预期权重以 $$$998244353$$$ 为模。
示例
输入 #1
2 1 0 1 2 1
输出 #1
332748119 332748119
输入 #2
1 2 1 1
输出 #2
3
输入 #3
3 3 0 1 1 4 3 5
输出 #3
160955686 185138929 974061117
注意
在第一个示例中,如果唯一一次访问以 $$$\frac 2 3$$$ 的概率显示第一张图片,则最终权重为 $$$(1,1)$$$;如果唯一一次访问以 $$$\frac1 3$$$ 的概率显示第二张图片,则最终权重为 $$$(2,2)$$$。
因此,两个预期权重均为 $$$\frac2 3\cdot 1+\frac 1 3\cdot 2=\frac4 3$$$ 。
因为 $$$332748119\cdot 3\equiv 4\pmod{998244353}$$$,您需要打印 $$$332748119$$$ 而不是 $$$\frac4 3$$$ 或 $$$1.3333333333$$$。
在第二个例子中,Nauuo 喜欢的图片只有一张,因此 Nauuo 每次访问网站时,$$$w_1$$$ 都会增加 $$$1$$$。
因此,预期重量为 $$$1+2=3$$$。
Nauuo 非常调皮,所以她没有给你任何关于第三个例子的提示。