#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=1010; int t,n,m,a[MAXN],b[MAXN],c[MAXN],A[MAXN],B[MAXN],C[MAXN]; map<int,int>mpa,mpb,mpc; int fa[MAXN][MAXN],fb[MAXN][MAXN],fc[MAXN][MAXN]; int f[MAXN],ans[MAXN][MAXN]; #define pii pair<int,int> #define fr first #define sc second #define mk make_pair void slv(){ scanf("%lld%lld%lld",&t,&n,&m); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } for(int i=1;i<=n;i++){ scanf("%lld",&b[i]); c[i]=a[i]+b[i]; } for(int i=n;i;i--){ mpa.clear(),mpb.clear(),mpc.clear(); mpa[0]=i-1;mpb[0]=i-1;mpc[0]=i-1; A[i-1]=B[i-1]=C[i-1]=0; for(int j=i;j<=n;j++){ A[j]=A[j-1]+a[j];B[j]=B[j-1]+b[j];C[j]=C[j-1]+c[j]; if(mpa.count(A[j]))fa[i][j]=max(fa[i][j-1],fa[i][mpa[A[j]]]+1); else fa[i][j]=fa[i][j-1]; if(mpb.count(B[j]))fb[i][j]=max(fb[i][j-1],fb[i][mpb[B[j]]]+1); else fb[i][j]=fb[i][j-1]; if(mpc.count(C[j]))fc[i][j]=max(fc[i][j-1],fc[i][mpc[C[j]]]+1); else fc[i][j]=fc[i][j-1]; mpb[B[j]]=j;mpa[A[j]]=j;mpc[C[j]]=j; } } for(int i=1;i<=n;i++){ for(int j=i;~j;j--){ f[i]=max(f[i],f[j]+max(fa[j+1][i]+fb[j+1][i],fc[j+1][i])); } } for(int i=0;i<=n;i++){ for(int p=i;p<=n;p++){ for(int q=i;q<=n;q++){ ans[p][q]=max(ans[p][q],f[i]+fa[i+1][p]+fb[i+1][q]); } } } int sum=0; for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ sum+=ans[i][j]; } } if(t)printf("%lld\n",sum); for(int i=1;i<=m;i++){ int x,y; scanf("%lld%lld",&x,&y); printf("%lld\n",ans[x][y]); } } signed main(){ slv(); return 0; }