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