E. Expected Damage SOLUTIONS CODE FROCES

Expected Damage SOLUTION

You are playing a PC game. In this game, you need to battle n beasts. To guard from beasts, you need a shield. Each shield has two boundaries: its present toughness an and its protection rating b. Every beast has just a single boundary: its quality d.

At the point when you battle a beast with quality d while having a shield with current sturdiness an and guard b, there are three potential results:

on the off chance that a=0, at that point you get d harm;

on the off chance that a>0 and d≥b, you get no harm, yet the current toughness of the shield diminishes by 1;

in the event that a>0 and d<b, nothing occurs. The I-th beast has quality di, and you will battle every one of the beasts precisely once, in some arbitrary request (all n! orders are equiprobable). You need to consider m various shields, the I-th shield has starting solidness ai and guard rating bi. For each shield, compute the normal measure of harm you will get in the event that you take this shield and battle the given n beasts in arbitrary request.

Information

The main line contains two numbers n and m (1≤n,m≤2⋅105) — the quantity of beasts and the quantity of shields, individually.

The subsequent line contains n numbers d1, d2, …, dn (1≤di≤109), where di is the quality of the I-th beast.

At that point m lines follow, the I-th of them contains two numbers ai and bi (1≤ai≤n; 1≤bi≤109) — the portrayal of the I-th shield.

Yield

Print m numbers, where the I-th whole number speaks to the normal harm you get with the I-th shield as follows: it very well may be demonstrated that, for each shield, the normal harm is a final part xy, where y is coprime with 998244353. You need to print the estimation of x⋅y−1mod998244353, where y−1 is the backwards component for y (y⋅y−1mod998244353=1).

Models

input

3 2

1 3 1

2 1

1 2

output

665496237

1

input

3

4 2 6

3 1

1 2

2 3

output

0

8

665496236

We are Live Join Us 
Check Your Mails

Leave a Comment