MOD = 998244353
N,M,Q = map(int,input().split())
A = list(map(int,input().split()))
A = [A[i]-1 for i in range(N)]
B = [0]*N
B[-1] = A[-1]
for i in range(N-2,-1,-1):
    B[i] = (B[i+1]+A[i]*pow(M,N-1-i,MOD))%MOD
for _ in range(Q):
    l,r = map(int,input().split())
    l -= 1
    if r==N:
        a = B[l]
    else:
        a = (B[l]-B[r])
        k = pow(M,N-r,MOD)
        a = (a*pow(k,MOD-2,MOD))%MOD
    print((a+1)%MOD)