#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define lc(x) (x<<1) #define rc(x) (x<<1|1) #define p1(x) x.first #define p2(x) x.second #define endl "\n" int t,n,m; int p[3][1000300]; int c[3][1000200]; int s[2][1000300]; map<int,int>mp; inline void cc(int *p,int *c){ mp.clear(); int s=0; for(int i=1;i<=n;i++)p[i]+=p[i-1]; mp[p[n]]=n; for(int i=n-1;i>=0;i--){ if(mp.count(p[i])) c[i]=mp[p[i]]; else c[i]=n+1; mp[p[i]]=i; } } int f[1010][1010]; inline void chkmx(int &x,int y){ x=max(x,y); } int A[1000300]; int mat[2][1000300]; signed main() { // freopen("zero.in","r",stdin); // freopen("zero.out","w",stdout); ios::sync_with_stdio(0); cin>>t>>n>>m; for(int i=1;i<=n;i++)cin>>s[0][i],p[0][i]=s[0][i]; for(int i=1;i<=n;i++)cin>>s[1][i],p[1][i]=s[1][i]; for(int i=1;i<=n;i++)p[2][i]=s[1][i]+s[0][i]; for(int i=0;i<3;i++) cc(p[i],c[i]); if(n<=1000){ int res=0; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++){ chkmx(f[i+1][j],f[i][j]); chkmx(f[i][j+1],f[i][j]); chkmx(f[c[0][i]][j],f[i][j]+1); chkmx(f[i][c[1][j]],f[i][j]+1); int t=c[2][max(i,j)]; chkmx(f[t][t],f[i][j]+1); res+=f[i][j]; } if(t)cout<<res<<endl; while(m--){ int x,y; cin>>x>>y; cout<<f[x][y]<<endl; } } else if(t==0){ while(m--){ int x,y; cin>>x>>y; } } cout.flush(); return 0; } /* 1 6 5 70 70 70 70 70 -15 90 -60 -30 30 -30 15 3 4 5 5 2 6 6 4 6 6 */