A13856 | 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 > 0$ and $d \ge b$ , you receive no damage, but the current durability of the shield decreases by $1$ ;
- if $a > 0$ and $d < 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.

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.

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$ ).