CF1172C2 Nauuo and Pictures (hard version)

简单版与困难版的唯一区别在于数据范围。 Nauuo 是一个喜欢随机图片网站的女孩。 有一天，她自己制作了一个包含 $n$ 张图片的随机图片网站。 当 Nauuo 访问该网站时，她会看到且仅看到一张图片。网站展示每张图片的概率并不相同。第 $i$ 张图片有一个非负权值 $w_i$，第 $i$ 张图片被展示的概率为 $\frac{w_i}{\sum_{j=1}^n w_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 2 \times 10^5$，$1 \le m \le 3000$）——图片的数量和访问网站的次数。 第二行包含 $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$（$w_i \geq 1$）——每张图片的初始权值。保证所有初始权值之和不超过 $998244352 - m$。

输出 $n$ 个整数 $r_1, r_2, \ldots, r_n$，表示每张图片的期望权值对 $998244353$ 取模后的结果。

在第一个样例中，如果唯一一次访问展示了第一张图片，概率为 $\frac{2}{3}$，最终权值为 $(1,1)$；如果展示了第二张图片，概率为 $\frac{1}{3}$，最终权值为 $(2,2)$。 因此，两张图片的期望权值都是 $\frac{2}{3} \cdot 1 + \frac{1}{3} \cdot 2 = \frac{4}{3}$。 因为 $332748119 \cdot 3 \equiv 4 \pmod{998244353}$，所以你需要输出 $332748119$，而不是 $\frac{4}{3}$ 或 $1.3333333333$。 在第二个样例中，只有一张图片是 Nauuo 喜欢的，所以每次访问都会将 $w_1$ 增加 $1$。 因此，期望权值为 $1 + 2 = 3$。 Nauuo 很调皮，所以她没有给出第三个样例的任何提示。 由 ChatGPT 4.1 翻译