代码制作不易，点个赞再走吧QwQ

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define ull unsigned lint
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define gc getchar()
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
inline int inn()
{
    int x,ch;while((ch=gc)<'0'||ch>'9');
    x=ch^'0';while((ch=gc)>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^'0');return x;
}
const int N=110,M=10010,T=1100000,LOG=12;
namespace RND_space{
    unsigned int SA,SB,SC,t;int lim;inline int _init() { return scanf("%u%u%u%d",&SA,&SB,&SC,&lim),0; }
    inline int rnd() { return SA^=SA<<16,SA^=SA>>5,SA^=SA<<1,t=SA,SA=SB,SB=SC,SC^=t^SA,int(SC%lim+1); }
}using RND_space::rnd;
int r[M][N],d[M][N],P[M][N];lint ps[M],ss[M];
struct E{
    int w,x,y;
    E(int _w=0,int _x=0,int _y=0) { w=_w,x=_x,y=_y; }
    inline bool operator<(const E &e)const { return w<e.w; }
};vector<E> pre[M],suf[M],cur;vector<int> g[T];
int up[T][LOG],Log[N<<2],in[T],fa[T],dpt[T],dfc,val[T],lst[N<<1];
inline int _init_Log(int n) { rep(i,2,n) Log[i]=Log[i>>1]+1;return 0; }
int dfs(int x)
{
    in[x]=++dfc,memset(up[x]+1,0,sizeof(int)*(LOG-1));int y;
    for(int i=1;i<=Log[dpt[x]];i++) up[x][i]=up[up[x][i-1]][i-1];
    Rep(i,g[x]) y=g[x][i],dpt[y]=dpt[x]+1,up[y][0]=x,dfs(y);return 0;
}
inline int incmp(int x,int y) { return in[x]<in[y]; }
inline int getLCA(int x,int y)
{
    if(dpt[x]<dpt[y]) swap(x,y);
    for(int i=Log[dpt[x]];i>=0;i--)
        if(dpt[up[x][i]]>=dpt[y]) x=up[x][i];
    if(x==y) return x;
    for(int i=Log[dpt[x]];i>=0;i--)
        if(up[x][i]^up[y][i]) x=up[x][i],y=up[y][i];
    return up[x][0];
}
inline int clrfa(vector<E> &v)
{
    int mx=0,x,y;
    Rep(i,v)
        x=v[i].x,fa[x]=x,vector<int>().swap(g[x]),mx=max(mx,x),
        y=v[i].y,fa[y]=y,vector<int>().swap(g[y]),mx=max(mx,y);
    return mx;
}
inline int findf(int x) { return x==fa[x]?x:fa[x]=findf(fa[x]); }
inline lint ins(int n,int *P,int *X,int *Y,int *d,int *r,vector<E> &ans)
{
    lint res=0;Rep(i,cur) res-=cur[i].w;
    rep(i,1,n) cur.pb(E(r[i],X[i],Y[i]));
    rep(i,1,n-1) cur.pb(E(d[i],Y[i],Y[i+1]));
    sort(cur.begin(),cur.end());int nc=clrfa(cur);
    Rep(i,cur)
    {
        int x=findf(cur[i].x),y=findf(cur[i].y),w=cur[i].w;if(x==y) continue;
        fa[x]=fa[y]=++nc,fa[nc]=nc,vector<int>().swap(g[nc]),g[nc].pb(x),g[nc].pb(y),val[nc]=w,res+=w;
    }
    dfc=0,up[nc][0]=0,dpt[nc]=0,dfs(nc);
    int lc=0;rep(i,1,n) lst[++lc]=P[i];
    sort(lst+1,lst+lc+1,incmp),ans.clear();
    rep(i,1,lc-1) ans.pb(E(getLCA(lst[i],lst[i+1])[val],lst[i],lst[i+1]));
    
    rep(i,1,n) lst[++lc]=Y[i];
    sort(lst+1,lst+lc+1,incmp),vector<E>().swap(cur);
    rep(i,1,lc-1) cur.pb(E(getLCA(lst[i],lst[i+1])[val],lst[i],lst[i+1]));
    return res;
}
inline lint solve(vector<E> &pre,vector<E> &suf,int n,int m)
{
    cur=pre;Rep(i,suf) cur.pb(suf[i]);
    lint res=0;Rep(i,cur) res-=cur[i].w;
    rep(i,1,n) cur.pb(E(r[m][i],P[m][i],P[1][i]));
    clrfa(cur),sort(cur.begin(),cur.end());
    Rep(i,cur)
    {
        int x=findf(cur[i].x),y=findf(cur[i].y);
        if(x^y) fa[x]=y,res+=cur[i].w;
    }
    return res;
}
int main()
{
    int n=inn(),m=inn(),cnt=0;
    RND_space::_init(),_init_Log(n<<2);
    rep(i,1,n) rep(j,1,m) r[j][i]=rnd();
    rep(i,1,n-1) rep(j,1,m) d[j][i]=rnd();
    rep(i,1,m) rep(j,1,n) P[i][j]=++cnt;
    
    rep(i,1,n-1) cur.pb(E(d[1][i],P[1][i],P[1][i+1]));
    Rep(i,cur) ps[1]+=cur[i].w;pre[1]=cur;
    rep(i,2,m) ps[i]=ps[i-1]+ins(n,P[1],P[i-1],P[i],d[i],r[i-1],pre[i]);
    
    cur.clear();rep(i,1,n-1) cur.pb(E(d[m][i],P[m][i],P[m][i+1]));
    Rep(i,cur) ss[m]+=cur[i].w;suf[m]=cur;
    for(int i=m-1;i;i--) ss[i]=ss[i+1]+ins(n,P[m],P[i+1],P[i],d[i],r[i],suf[i]);
    for(int q=inn(),l,r;q;q--)
        l=inn()-1,r=inn()+1,printf("%lld\n",ps[l]+ss[r]+solve(pre[l],suf[r],n,m));
    return 0;
}