Expected Damage
Description
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$).
Input
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.
Output
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$).
Samples
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