#define MD 998244353
ll@N,@M,@Q,@A--[N];Mint m=M,B[N+1]{};rep(i,N)B[i+1]=B[i]*m+A[i];rep(Q){ll@--l,@r;wt(B[r]-B[l]*m**(r-l)+1);}