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.


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


-----Examples-----
Input
3 2
1 3 1
2 1
1 2

Output
665496237
1

Input
3 3
4 2 6
3 1
1 2
2 3

Output
0
8
665496236

Difficulty: interview

Starter code:

Solutions:
import sys,bisect
input = sys.stdin.readline

MOD = 998244353
def frac(a,b):
    inv = pow(b, MOD - 2, MOD)
    return (a * inv) % MOD

n, m = list(map(int, input().split()))
d = list(map(int, input().split()))
d.sort()
tot = sum(d)

pref = [0]
for v in d:
    pref.append(pref[-1] + v)

out = [0] * m
for _ in range(m):
    a, b = list(map(int, input().split()))
    ind = bisect.bisect_left(d, b)
    sum_before = pref[ind]
    rest = tot - pref[ind]

    if a <= (n - ind):
        out[_] += sum_before * frac(n - ind - a + 1 ,n - ind + 1)
        out[_] += rest * frac(n - ind - a ,n - ind)
        out[_] %= MOD
print('\n'.join(map(str,out)))


import sys,bisect
M=998244353
y=lambda:map(int,sys.stdin.readline().split())
n,m=y()
d=sorted(y())
p=[0]
for i in d:p.append(p[-1]+i)
for _ in range(m):
 a,b=y()
 i=bisect.bisect_left(d,b)
 if n-i<a:print(0);continue
 print(((n-i-a+1)*p[i]*pow(n-i+1,M-2,M)+(n-i-a)*(p[-1]-p[i])*pow(n-i,M-2,M))%M)

import sys,bisect
input = sys.stdin.readline
MOD = 998244353
def frac(a,b):return(a*pow(b,MOD-2,MOD))%MOD
n,m=map(int, input().split())
d=sorted(list(map(int, input().split())))
tot=sum(d)
pref=[0]
for v in d:pref.append(pref[-1] + v)
out=[0]*m
for _ in range(m):
 a,b=map(int,input().split())
 ind=bisect.bisect_left(d,b)
 sum_before=pref[ind]
 rest=tot-pref[ind]
 if a<=n-ind:
  out[_]+=sum_before * frac(n-ind-a+1,n-ind+1)
  out[_]+=rest*frac(n-ind-a,n-ind)
  out[_]%=MOD
print('\n'.join(map(str,out)))

import sys,bisect
input=sys.stdin.readline
MOD=998244353
def f(a,b):return a*pow(b,MOD-2,MOD)
n,m=map(int,input().split())
d=sorted(map(int,input().split()))
pref=[0]
for v in d:pref.append(pref[-1] + v)
out=[0]*m
for _ in range(m):
 a,b=map(int,input().split());i=bisect.bisect_left(d,b)
 if a<=n-i:out[_]=(pref[i]*f(n-i-a+1,n-i+1)+(pref[-1]-pref[i])*f(n-i-a,n-i))%MOD
print('\n'.join(map(str,out)))

import sys,bisect
M=998244353
y=lambda:map(int,sys.stdin.readline().split())
n,m=y()
d=sorted(y())
p=[0]
for i in d:p+=[p[-1]+i]
for _ in range(m):a,b=y();i=bisect.bisect_left(d,b);print(0 if n-i<a else((n-i-a+1)*p[i]*pow(n-i+1,M-2,M)+(n-i-a)*(p[-1]-p[i])*pow(n-i,M-2,M))%M)


import sys;input=sys.stdin.readline
mod = 998244353
#mod=10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%mod
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], mod -2, mod)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % mod
    return frac, fraci
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, pow(b, mod-2,mod))
#frac, fraci = frac(141398)
#print(fraci)

N, M = list(map(int, input().split()))
X = list(map(int, input().split()))
t = []
for i in range(N):
    t.append((0, X[i]))
Q = []
for i in range(M):
    a, b = list(map(int, input().split()))
    Q.append((a, b))
    t.append((1, b))

Y = [0]*(N+M)
Z = [0]*(N+M)
t.sort(key=lambda x:x[1])
d = dict()
d2 = [0]*(N+M)
cnt = 0
for l, x in t:
    if x not in d:
        cnt += 1
        d[x] = cnt
        d2[cnt] = x
    if not l:
        Y[cnt] += 1
for i in range(N+M):
    Z[i] = Y[i]*d2[i]
Y.append(0)
Z.append(0)
for i in range(N+M-1, -1, -1):
    Y[i] = Y[i+1]+Y[i]
    Z[i] = Z[i+1]+Z[i]

for a, b in Q:
    k=Y[d[b]]
    R = 0
    if k>a:
        R += div((k-a),k)*Z[d[b]]
    if k+1>a:
        R += div((k+1-a),k+1)*(Z[0]-Z[d[b]])
    print(R%mod)


import sys,bisect
r=lambda:map(int,sys.stdin.readline().split())
M=998244353
def f(b):return pow(b,M-2,M)
n,m=r()
d=sorted(r())
p=[0]
for v in d:p+=[p[-1]+v]
o=[0]*m
for _ in range(m):
 a,b=r();i=bisect.bisect_left(d,b);v=n-i
 if a<=v:o[_]=(p[i]*a*f(v+v*v)-p[-1]*(a*f(v)-1))%M
print('\n'.join(map(str,o)))

import sys,bisect
r=lambda:map(int,sys.stdin.readline().split())
M=998244353
def f(b):return pow(b,M-2,M)
n,m=r()
d=sorted(r())
p=[0]
for v in d:p+=[p[-1]+v]
for _ in range(m):
 a,b=r();i=bisect.bisect_left(d,b);v=n-i
 print([(p[i]*a*f(v+v*v)-p[-1]*(a*f(v)-1))%M,0][a>v])

import sys,bisect
r=lambda:map(int,sys.stdin.readline().split())
M=998244353
def f(b):return pow(b,M-2,M)
n,m=r()
d=sorted(r())
p=[0]
for v in d:p+=[p[-1]+v]
for _ in range(m):a,b=r();i=bisect.bisect_left(d,b);v=n-i; print([(p[i]*a*f(v+v*v)-p[-1]*(a*f(v)-1))%M,0][a>v])

import sys,bisect
M=998244353
y=lambda:map(int,sys.stdin.readline().split())
n,m=y()
d=sorted(y())
p=[0]
for i in d:p+=[p[-1]+i]
for _ in range(m):a,b=y();i=bisect.bisect_left(d,b);v=n-i;print(0 if n-i<a else((v-a+1)*p[i]*pow(v+1,M-2,M)+(v-a)*(p[-1]-p[i])*pow(v,M-2,M))%M)

import sys,bisect
r=lambda:map(int,sys.stdin.readline().split())
M=998244353
def f(b):return pow(b,M-2,M)
n,m=r()
d=sorted(r())
p=[0]
for v in d:p+=[p[-1]+v]
for _ in range(m):a,b=r();i=bisect.bisect(d,b-1);v=n-i; print([(p[i]*a*f(v+v*v)-p[-1]*(a*f(v)-1))%M,0][a>v])

import sys,bisect
r=lambda:map(int,sys.stdin.readline().split())
M=998244353
f=lambda b:pow(b,M-2,M)
n,m=r()
d=sorted(r())
p=[0]
for v in d:p+=[p[-1]+v]
for _ in range(m):a,b=r();i=bisect.bisect_left(d,b);v=n-i;print([(p[i]*a*f(v+v*v)-p[-1]*(a*f(v)-1))%M,0][a>v])

import sys,bisect
r=lambda:map(int,sys.stdin.readline().split())
M=998244353
f=lambda b:pow(b,M-2,M)
n,m=r()
d=sorted(r())
p=[0]
for v in d:p+=[p[-1]+v]
for _ in range(m):a,b=r();i=bisect.bisect(d,b-1);v=n-i;print([(p[i]*a*f(v+v*v)-p[-1]*(a*f(v)-1))%M,0][a>v])

import sys,bisect
r=lambda:map(int,sys.stdin.readline().split())
M=998244353
f=lambda b:pow(b,M-2,M)
n,m=r()
d=sorted(r())
p=[0]
for v in d:p+=[p[-1]+v]
for _ in range(m):a,b=r();i=bisect.bisect(d,b-1);v=n-i; print([(p[i]*a*f(v+v*v)-p[-1]*(a*f(v)-1))%M,0][a>v])

import sys
from sys import stdin
import bisect

def inverse(a,mod):
    return pow(a,mod-2,mod)

def modfac(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs

def modnCr(n,r):
    return fac[n] * inv[n-r] * inv[r] % mod

mod = 998244353
fac,inv = modfac(3*10**5,mod)

n,m = list(map(int,stdin.readline().split()))
d = list(map(int,stdin.readline().split()))
d.sort()
dsum = sum(d)
s = [0]
for i in range(n):
    s.append(s[-1] + d[i])

aaa = []
for loop in range(m):

    a,b = list(map(int,stdin.readline().split()))

    X = bisect.bisect_left(d , b)
    Y = n-X

    xsum = s[X]
    ysum = dsum-xsum

    #print (X,Y,xsum,ysum,file=sys.stderr)

    ans = 0
    if a <= Y:
        ans += ysum * fac[n] * (Y-a) * inverse(Y,mod)
        ans += xsum * fac[n] * (Y-a+1) * inverse(Y+1,mod)
        ans %= mod

    aaa.append (ans * inv[n] % mod)

print("\n".join(map(str,aaa)))