CF1418E.Expected Damage

You are playing a computer game. In this game, you have to fight $n$ monsters.

To defend from monsters, you need a shield. Each shield has two parameters: its current durability $a$ and its defence rating $b$. Each monster has only one parameter: its strength $d$.

When you fight a monster with strength $d$ while having a shield with current durability $a$ and defence $b$, there are three possible outcomes:

• if $a = 0$, then you receive $d$ damage;
• if $a \gt 0$ and $d \ge b$, you receive no damage, but the current durability of the shield decreases by $1$;
• if $a \gt 0$ and $d \lt b$, nothing happens.

The $i$-th monster has strength $d_i$, and you will fight each of the monsters exactly once, in some random order (all $n!$ orders are equiprobable). You have to consider $m$ different shields, the $i$-th shield has initial durability $a_i$ and defence rating $b_i$. For each shield, calculate the expected amount of damage you will receive if you take this shield and fight the given $n$ monsters in random order.

你正在玩一款电脑游戏。在这款游戏中，你需要与 $n$ 只怪物战斗。

为了抵御怪物，你需要一面盾牌。每面盾牌有两个参数：当前耐久度 $a$ 和防御等级 $b$。每只怪物只有一个参数：其力量值 $d$。

当你使用当前耐久度为 $a$、防御等级为 $b$ 的盾牌与力量值为 $d$ 的怪物战斗时，会出现以下三种可能的结果：

• 若 $a = 0$，则你受到 $d$ 点伤害；
• 若 $a \gt 0$ 且 $d \ge b$，则你不受到任何伤害，但盾牌的当前耐久度减少 $1$；
• 若 $a \gt 0$ 且 $d \lt b$，则什么也不会发生。

第 $i$ 只怪物的力量值为 $d_i$，你将恰好与每只怪物战斗一次，且战斗顺序是随机的（所有 $n!$ 种排列等概率）。你共有 $m$ 面不同的盾牌可供选择，其中第 $i$ 面盾牌的初始耐久度为 $a_i$、防御等级为 $b_i$。对每面盾牌，请计算：若选用该盾牌，并以随机顺序与给定的 $n$ 只怪物战斗，你所受伤害的期望值。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of monsters and the number of shields, respectively.

The second line contains $n$ integers $d_1$, $d_2$, ..., $d_n$ ($1 \le d_i \le 10^9$), where $d_i$ is the strength of the $i$-th monster.

Then $m$ lines follow, the $i$-th of them contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n$; $1 \le b_i \le 10^9$) — the description of the $i$-th shield.

第一行包含两个整数 $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$ 个盾牌的描述。

Print $m$ integers, where the $i$-th integer represents the expected damage you receive with the $i$-th shield as follows: it can be proven that, for each shield, the expected damage is an irreducible fraction $\dfrac{x}{y}$, where $y$ is coprime with $998244353$. You have to print the value of $x \cdot y^{-1} \bmod 998244353$, where $y^{-1}$ is the inverse element for $y$ ($y \cdot y^{-1} \bmod 998244353 = 1$).

输出 $m$ 个整数，其中第 $i$ 个整数表示使用第 $i$ 个护盾时你所受到的期望伤害。可以证明：对于每个护盾，其期望伤害均为一个既约分数 $\dfrac{x}{y}$，其中 $y$ 与 $998244353$ 互质。你需要输出 $x \cdot y^{-1} \bmod 998244353$ 的值，其中 $y^{-1}$ 是 $y$ 的模 $998244353$ 乘法逆元（即满足 $y \cdot y^{-1} \bmod 998244353 = 1$）。