C2. Nauuo и картинки (усложненная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие этой версии от упрощенной это ограничения.

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 2\cdot 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$$$.

Примеры
Входные данные
2 1
0 1
2 1
Выходные данные
332748119
332748119
Входные данные
1 2
1
1
Выходные данные
3
Входные данные
3 3
0 1 1
4 3 5
Выходные данные
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, таким образом после каждого посещения $$$w_1$$$ будет увеличено на $$$1$$$.

Таким образом, ожидаемый вес равен $$$1+2=3$$$.

Nauuo очень капризная, поэтому она отказалась давать вам какие-либо подсказки по третьему примеру.