#include <cassert>
#include <cstdio>
#include "lottery.h"
//#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define defN 200001
typedef long long ll;
vector<int>reds,blues;
int n;
bool checkers(ll lsz, ll x, vector<pair<ll,ll>>& stuffs)
{
ll ni=x*lsz;ni/=2;
ll bno=0,rno=0,cno=0,dbs=0;
for(pair<ll,ll> num:stuffs)
{
num.ff=min(num.ff,x);num.ss=min(num.ss,x);
ll amt=min(num.ff,num.ss);
cno+=amt;
bno+=(num.ss-amt);
rno+=(num.ff-amt);
ll takemore=max(num.ss,num.ff);
if(takemore<x)
{
cno-=min(amt,x-takemore);
dbs+=min(amt,x-takemore);
}
//if(x==2){debu3(num.ff,num.ss,amt);debu2(num.ss-amt,num.ff-amt);}
}
rno=min(rno,ni);bno=min(bno,ni);
ll t1=ni-rno;
t1-=min(t1,dbs);
cno-=t1;
if(cno<0)return false;
t1=ni-bno;
t1-=min(t1,dbs);
cno-=t1;
if(cno<0)return false;
return true;
}
void init(int N, int Q, vector<int> X, vector<int> Y)
{
reds=X;blues=Y;
n=N;
}
int max_prize(int L, int R)
{
vector<pair<ll,ll>>stuffs;
for(int a=L;a<=R;a++)
{
stuffs.pb(mp(reds[a],blues[a]));
}
ll hi=1000000001,lo=0,mid;
while(hi>lo+1)
{
mid=(lo+hi)/2;
if(checkers(R-L+1,mid,stuffs))
{
lo=mid;
}
else
{
hi=mid;
}
}
return lo;
}
int main() {
int N, Q;
assert(scanf("%d %d", &N, &Q) == 2);
std::vector<int> X(N), Y(N);
for (int i = 0; i < N; i++) { assert(scanf("%d", &X[i]) == 1); }
for (int i = 0; i < N; i++) { assert(scanf("%d", &Y[i]) == 1); }
init(N, Q, X, Y);
for (int k = 0; k < Q; k++) {
int L, R;
assert(scanf("%d %d", &L, &R) == 2);
printf("%d\n", max_prize(L, R));
fflush(stdout);
}
}
