有点牛的题。
一个可能比较前置的技巧是 LCT 维护 MST 的方法，具体来说就是加边的时候，如果两边原本就是连通的，那么就把路径上的最大边权拿出来和要加的边进行比较，选择更优的那一个。这个技巧启示我们，在 MST 中只有任意两点的路径的最大边权是重要的，并且两张图的 MST 是支持进行合并的。
所以说，一个基本的思路是预处理出所有前缀和后缀对应的 MST 然后在查询的时候进行合并，但是总的点数是 \(n^2m\) 的，显然无法通过。
但是同时我们还注意到一个性质：这张图是一个网格图。这也就意味着，一个前缀/后缀形成的最小生成树，第 \(i\) 列和第 \(i+2\) 列的点是完全没有连边的。所以对于前缀/后缀的最小生成树，只有第一列和最后一列的点是重要的，那这不就是虚树吗？于是有一个朴素的做法，大力维护每个前缀/后缀的虚树然后在最后进行合并就可以了。
但是事实上这个虚树是不用真正建出来的，有一种基于并查集的更加方便的做法。具体来说，我们假设已经知道了前 \(i-1\) 列形成的 MST，我们现在要加到第 \(i\) 列，显然我们应该直接把原本两棵 MST 的边与连接两边的边一起做 Kruskal，但是为了控制点数，在这个过程中我们不希望第 \(i-1\) 列的点出现在新的 MST 中，所以并查集合并的时候，如果有一个集合里没有任何一个第一列或第 \(m\) 列的点，那么他就是不需要真正加入新 MST 中的边。但是它已经确定加入了贡献里且不再会被踢出，所以我们需要把它的边权累加进答案，然后把父亲指向有第一列或第 \(m\) 列的点的集合。否则，可以证明直接连接两个集合的祖先节点是等价的，然后把这条边加入新的边集即可。
具体来说，因为 MST 中只关心任意两点的路径的最大边权，且在 Kruskal 的过程中这条边一定是最大的，所以在两个集合中无论怎么连都能够保证路径的最大边权，所以起到的效果是等价的。
所以我们可以直接用并查集维护前后缀的 MST，询问时暴力合并即可 。
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
namespace IN{
const int Q = 1000000;
#define getc() (p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,Q),p1==p2)?EOF:*p1++)
char buf[Q],*p1,*p2;
template<typename T>inline bool read(T &x) {
static std::streambuf *inbuf=cin.rdbuf();
x=0;
register int f=0,flag=false;
register char ch=getc();
while(!isdigit(ch)){
if (ch=='-') f=1;
ch=getc();
}
if(isdigit(ch)) x=x*10+ch-'0',ch=getc(),flag=true;
while(isdigit(ch)) {
x=x*10+ch-48;
ch=getc();
}
x=f?-x:x;
return flag;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args) {
return read(a)&&read(args...);
}
#undef getc
}
using namespace IN;
const int N=105,M=10005;
int n,m,q,r[N][M],c[N][M];
unsigned int SA, SB, SC;int lim;
int getweight() {
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC % lim + 1;
}
void gen() {
scanf("%d%d%u%u%u%d", &n, &m, &SA, &SB, &SC, &lim);
int i, j, w;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++) {
// w = getweight();
// if (j < m) {
// addedge(i, j, i, j + 1, w);
// } else {
// addedge(i, j, i, 1, w);
// }
r[i][j]=getweight();
}
for(i = 1; i < n; i++)
for(j = 1; j <= m; j++) {
// w = getweight();
c[i][j]=getweight();
// addedge(i, j, i + 1, j, w);
}
}
struct edge{
int u,v,w;
};
inline int getid(int x,int y){
return (x-1)*m+y;
}
struct MST{
long long sum;
vector<edge>vec;
MST(){sum=0;}
MST(int id){
sum=0;
for(signed i=1;i<n;++i)vec.push_back({getid(i,id),getid(i+1,id),c[i][id]});
}
void print(){
cout<<"CHECK\n";
cout<<"SUM = "<<sum<<'\n';
for(auto x:vec)cout<<x.u<<' '<<x.v<<' '<<x.w<<'\n';
}
}pre[M],suf[M];
int fa[N*M];
bool flg[N*M];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
MST merge(int id,bool opt){
MST ans;
ans.vec.clear();
vector<edge>vec;
for(signed i=1;i<=n;++i)fa[getid(i,id)]=getid(i,id),flg[getid(i,id)]=1;
if(!opt){
for(signed i=1;i<=n;++i){
fa[getid(i,id-1)]=getid(i,id-1);
flg[getid(i,id-1)]=0;
fa[getid(i,1)]=getid(i,1);
flg[getid(i,1)]=1;
}
}
else{
for(signed i=1;i<=n;++i){
fa[getid(i,id+1)]=getid(i,id+1);
flg[getid(i,id+1)]=0;
fa[getid(i,m)]=getid(i,m);
flg[getid(i,m)]=1;
}
}
if(!opt)for(auto x:pre[id-1].vec)vec.push_back(x);
else for(auto x:suf[id+1].vec)vec.push_back(x);
for(signed i=1;i<n;++i)vec.push_back({getid(i,id),getid(i+1,id),c[i][id]});
if(!opt)for(signed i=1;i<=n;++i)vec.push_back({getid(i,id-1),getid(i,id),r[i][id-1]});
else for(signed i=1;i<=n;++i)vec.push_back({getid(i,id),getid(i,id+1),r[i][id]});
sort(vec.begin(),vec.end(),cmp);
if(!opt)ans.sum=pre[id-1].sum;
else ans.sum=suf[id+1].sum;
for(auto x:vec){
int a=find(x.u),b=find(x.v),c=x.w;
if(a==b)continue;
if(!flg[a]||!flg[b])ans.sum+=c;
if(!flg[a])fa[a]=b;
else if(!flg[b])fa[b]=a;
else fa[b]=a,ans.vec.push_back({a,b,c});
}
return ans;
}
long long solve(int l,int r){
//do sth.
for(signed i=1;i<=n;++i)fa[getid(i,1)]=getid(i,1),fa[getid(i,l-1)]=getid(i,l-1),fa[getid(i,r+1)]=getid(i,r+1),fa[getid(i,m)]=getid(i,m);
vector<edge>vec;
for(auto x:pre[l-1].vec)vec.push_back(x);
for(auto x:suf[r+1].vec)vec.push_back(x);
for(signed i=1;i<=n;++i)vec.push_back({getid(i,1),getid(i,m),::r[i][m]});
// for(auto x:vec)cout<<x.u<<' '<<x.v<<' '<<x.w<<'\n';
long long ans=pre[l-1].sum+suf[r+1].sum;
// cout<<ans<<'\n';
sort(vec.begin(),vec.end(),cmp);
for(auto x:vec){
int a=find(x.u),b=find(x.v),c=x.w;
if(a==b)continue;
fa[a]=b;
ans+=c;
// cout<<x.u<<' '<<x.v<<' '<<c<<'\n';
}
return ans;
}
signed main()
{
// freopen("ds.in","r",stdin);
// freopen("ds.out","w",stdout);
// cin>>n>>m>>op>>lim>>seed;
gen();
pre[1]=MST(1);
suf[m]=MST(m);
for(signed i=2;i<=m;++i)pre[i]=merge(i,0);
// for(signed i=1;i<=m;++i)pre[i].print();
for(signed i=m-1;i>=1;--i)suf[i]=merge(i,1);
// do sth.
// q=read();
read(q);
while(q--){
int l,r;
read(l);read(r);
// =read(),r=read();
printf("%lld\n",solve(l,r));
}
return 0;
}