E. Ожидаемый урон
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в компьютерную игру. В этой игре вам необходимо сразиться с $$$n$$$ монстрами.

Чтобы защищаться от монстров, вам нужен щит. У каждого щита есть два параметра: текущая прочность $$$a$$$ и уровень защиты $$$b$$$. У каждого монстра есть только один параметр: его сила $$$d$$$.

Если вы сражаетесь с монстром с силой $$$d$$$, используя щит с текущей прочностью $$$a$$$ и уровнем защиты $$$b$$$, возможны три исхода:

  • если $$$a = 0$$$, вы получаете $$$d$$$ урона;
  • если $$$a > 0$$$ и $$$d \ge b$$$, вы не получаете урона, но прочность щита уменьшается на $$$1$$$;
  • если $$$a > 0$$$ и $$$d < 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