Единственное отличие этой версии от усложненной это ограничения.
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\) целых чисел \(r_1,r_2,\ldots,r_n\) — ожидаемые веса по модулю \(998244353\).
Примечание
В первом примере если на единственном посещении, с вероятностью \(\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 очень капризная, поэтому она отказалась давать вам какие-либо подсказки по третьему примеру.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
0 1
2 1
|
332748119
332748119
|
|
2
|
1 2
1
1
|
3
|
|
3
|
3 3
0 1 1
4 3 5
|
160955686
185138929
974061117
|