#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q; ll a[maxn],b[maxn],c[maxn],sa[maxn],sb[maxn],sc[maxn],nxta[maxn],nxtb[maxn],nxtc[maxn]; int nxt[maxn][20]; ll sufb[maxn]; ll RES; struct qrys { int x,y;ll res; }Q[maxn]; struct node { int val,pos; node(int _val,int _pos){ val=_val,pos=_pos; }node(){val=pos=0;} }dp[maxn]; bool operator<(node a,node b){ if(a.val!=b.val)return a.val<b.val; return a.pos>b.pos; } void init(ll *a,ll *sa,ll *nxta){ up(i,1,n)sa[i]=sa[i-1]+a[i]; map<ll,int>mp; down(i,n,0){ if(!mp.count(sa[i]))nxta[i]=n+1;else nxta[i]=mp[sa[i]]; mp[sa[i]]=i; } down(i,n-1,0)nxta[i]=min(nxta[i],nxta[i+1]); } void cal(ll *nxta,ll *nxtb,bool op){ up(i,0,n)nxt[i][0]=nxtb[i];nxt[n+1][0]=n+1; up(i,1,19)up(j,0,n+1)nxt[j][i]=nxt[nxt[j][i-1]][i-1]; up(i,0,n)dp[i].val=dp[i].pos=0; up(i,0,n){ dp[i+1]=max(dp[i+1],dp[i]); if(nxtb[dp[i].pos]==i+1)dp[i+1]=max(dp[i+1],node(dp[i].val+1,i+1)); if(nxtc[i]!=n+1)dp[nxtc[i]]=max(dp[nxtc[i]],node(dp[i].val+1,nxtc[i])); if(nxta[i]!=n+1){ int tmp=dp[i].val+1; int now=i; down(j,19,0)if(nxt[now][j]<=nxta[i])now=nxt[now][j],tmp+=(1<<j); dp[nxta[i]]=max(dp[nxta[i]],node(tmp,now)); } } up(i,0,n+1)sufb[i]=0; down(i,n,0)sufb[i]=sufb[nxtb[i]]+n-nxtb[i]+1; up(i,0,n)RES+=dp[i].val*(n-i+(!op))+sufb[dp[i].pos]; up(i,1,q)if(op)swap(Q[i].x,Q[i].y); up(i,1,q){ if((!op)&&Q[i].x<=Q[i].y); else if(op&&Q[i].x<Q[i].y); else continue; Q[i].res=dp[Q[i].x].val; int now=dp[Q[i].x].pos; down(j,19,0)if(nxt[now][j]<=Q[i].y)Q[i].res+=(1<<j),now=nxt[now][j]; } } void slv(){ bool FL=read();n=read(),q=read(); up(i,1,n)a[i]=read();up(i,1,n)b[i]=read(),c[i]=a[i]+b[i]; init(a,sa,nxta),init(b,sb,nxtb),init(c,sc,nxtc); up(i,1,q)Q[i].x=read(),Q[i].y=read(); cal(nxta,nxtb,0),cal(nxtb,nxta,1); if(FL)printf("%lld\n",RES); up(i,1,q)printf("%lld\n",Q[i].res); }int main(){ // freopen("1.in","r",stdin); // freopen("zero.in","r",stdin); // freopen("zero.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }