N, M, Q = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
invM = [1]
inv = pow(M, -1, MOD)
accA = [0] * (N+1)
bai = 1
for i in reversed(range(N)):
    invM.append((invM[-1] * inv)%MOD)
    accA[i] = accA[i+1] + (A[i] - 1)*bai
    accA[i] %= MOD
    bai *= M
    bai %= MOD

for _ in range(Q):
    l, r = map(int, input().split())
    print(((accA[l-1] - accA[r])*invM[N-r] + 1)%MOD)