Вы играете в компьютерную игру. В этой игре вам необходимо сразиться с $$$n$$$ монстрами.
Чтобы защищаться от монстров, вам нужен щит. У каждого щита есть два параметра: текущая прочность $$$a$$$ и уровень защиты $$$b$$$. У каждого монстра есть только один параметр: его сила $$$d$$$.
Если вы сражаетесь с монстром с силой $$$d$$$, используя щит с текущей прочностью $$$a$$$ и уровнем защиты $$$b$$$, возможны три исхода:
Сила $$$i$$$-го монстра равна $$$d_i$$$, и вам придется сразиться со всеми монстрами в случайном порядке (все $$$n!$$$ порядков равновероятны). Вы можете использовать один из $$$m$$$ различных щитов, у $$$i$$$-го щита прочность изначально равна $$$a_i$$$, а уровень защиты равен $$$b_i$$$. Для каждого щита посчитайте математическое ожидание полученного урона, если вы сразитесь со всеми $$$n$$$ монстрами в случайном порядке, используя этот щит.
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — количество монстров и количество щитов, соответственно.
Во второй строке заданы $$$n$$$ целых чисел $$$d_1$$$, $$$d_2$$$, ..., $$$d_n$$$ ($$$1 \le d_i \le 10^9$$$), где $$$d_i$$$ — сила $$$i$$$-го монстра.
Затем следуют $$$m$$$ строк, в $$$i$$$-й из которых заданы два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i \le n$$$; $$$1 \le b_i \le 10^9$$$) — описание $$$i$$$-го щита.
Выведите $$$m$$$ целых чисел, $$$i$$$-е из которых соответствует математическому ожиданию урона, который вы получите, используя $$$i$$$-й щит, следующим образом: можно доказать, что для каждого щита ответ — это несократимая дробь $$$\dfrac{x}{y}$$$, где $$$y$$$ и $$$998244353$$$ — взаимно простые числа. Выведите значение $$$x \cdot y^{-1} \bmod 998244353$$$, где $$$y^{-1}$$$ — обратный элемент к $$$y$$$ ($$$y \cdot y^{-1} \bmod 998244353 = 1$$$).
3 2 1 3 1 2 1 1 2
665496237 1
3 3 4 2 6 3 1 1 2 2 3
0 8 665496236
Название |
---|