N, M, Q = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

ls = []
rs = []

for _ in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ls.append(l)
    rs.append(r)

for i in range(Q):
    l, r, = ls[i], rs[i]
    ans = 1
    p = 1
    for j in range(r-l+1):
        ans = (ans + (A[r-j]-1)*p) % MOD
        p = (p*M) % MOD
    print(ans)