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

mod=998244353
INV=pow(M,mod-2,mod)
S=[0]*(N+1)

x=1

for i in range(N-1,-1,-1):
    S[i]=(S[i+1]+x*(A[i]-1))%mod
    x=x*M%mod

for tests in range(Q):
    l,r=map(int,input().split())
    ANS=S[l-1]-S[r]

    print((ANS*pow(INV,N-r,mod)%mod+1)%mod)