#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
int N;
const int MXN = 1 << 18;
const int INF = 2e9;
int X[MXN], Y[MXN];
using ll = long long;
struct node {
ll sm = 0, cnt = 0;
int l = 0, r = 0;
};
vector<node> nodes(1);
int create_node() {
nodes.push_back({});
return nodes.size() - 1;
}
int pull(int l, int r) {
int nw = create_node();
nodes[nw].sm = nodes[l].sm + nodes[r].sm;
nodes[nw].cnt = nodes[l].cnt + nodes[r].cnt;
nodes[nw].l = l;
nodes[nw].r = r;
return nw;
}
int add(int k, int s, int h) {
if(h == -1) {
int u = create_node();
nodes[u] = nodes[s];
nodes[u].sm += k;
nodes[u].cnt++;
return u;
}
int l = nodes[s].l, r = nodes[s].r;
if((k>>h)&1) {
if(!r) r = create_node();
r = add(k, r, h-1);
} else {
if(!l) l = create_node();
l = add(k, l, h-1);
}
return pull(l, r);
}
void print(int s) {
if(s == 0) return;
int l = nodes[s].l, r = nodes[s].r;
print(l);
cout << "(" << nodes[s].cnt << " " << nodes[s].sm << ") ";
print(r);
}
int xrts[MXN + 1], yrts[MXN + 1];
int segt[2 * MXN];
void upd(int k, int x) {
k += MXN;
segt[k] = x;
while(k > 1) {
k /= 2;
segt[k] = min(segt[2 * k], segt[2 * k + 1]);
}
}
int query(int l, int r) {
l += MXN;
r += MXN + 1;
int mn = INF;
while(l < r) {
if(l&1) mn = min(mn, segt[l++]);
if(r&1) mn = min(mn, segt[--r]);
l /= 2, r /= 2;
}
return mn;
}
void init(int _N, int _Q, vector<int> _X, vector<int> _Y) {
N = _N;
for(int i = 0; i < N; i++) X[i] = _X[i];
for(int i = 0; i < N; i++) Y[i] = _Y[i];
xrts[0] = create_node();
yrts[0] = create_node();
for(int i = 0; i < N; i++) {
xrts[i + 1] = add(X[i], xrts[i], 30);
yrts[i + 1] = add(Y[i], yrts[i], 30);
}
for(int i = 0; i < N; i++) {
upd(i, X[i] + Y[i]);
}
}
bool check_price(int L, int R, int C) {
ll lsm = 0, rsm = 0;
for(int i = L; i <= R; i++) {
if(X[i] + Y[i] < C) return false;
ll x = min(X[i], C);
ll y = min(Y[i], C);
lsm += C - 2 * y;
rsm += 2 * x - C;
}
return lsm <= 0 && 0 <= rsm;
}
int max_prize(int L, int R) {
ll mnC = query(L, R);
ll C = 0;
array<int, 4> crts = {xrts[L], xrts[R + 1], yrts[L], yrts[R + 1]};
for(int i = 0; i < 4; i++) {
//print(crts[i]);
//cout << endl;
}
auto left = [&] (array<int, 4> crts) {
for(int& rt : crts) rt = nodes[rt].l;
return crts;
};
auto right = [&] (array<int, 4> crts) {
for(int& rt : crts) rt = nodes[rt].r;
return crts;
};
ll xcnt = 0;
ll xsm = 0;
ll ycnt = 0;
ll ysm = 0;
auto add = [&] (array<int, 4> crts, int m) {
xcnt -= nodes[crts[0]].cnt * m;
xsm -= nodes[crts[0]].sm * m;
xcnt += nodes[crts[1]].cnt * m;
xsm += nodes[crts[1]].sm * m;
ycnt -= nodes[crts[2]].cnt * m;
ysm -= nodes[crts[2]].sm * m;
ycnt += nodes[crts[3]].cnt * m;
ysm += nodes[crts[3]].sm * m;
};
auto check = [&] () {
ll xocnt = R + 1 - L - xcnt;
ll xv = 2 * xsm - C * xcnt + C * xocnt;
ll yocnt = R + 1 - L - ycnt;
ll yv = C * ycnt - 2 * ysm - C * yocnt;
return yv <= 0 && 0 <= xv;
};
for(int h = 30; h >= 0; h--) {
if(C + (1 << h) > mnC) {
crts = left(crts);
continue;
}
add(left(crts), 1);
//for(int i = 0; i < 4; i++) cout << crts[i] << " ";
//cout << endl;
C += 1 << h;
//check_price(L, R, C);
if(check()) {
crts = right(crts);
} else {
crts = left(crts);
add(crts, -1);
C -= 1 << h;
}
}
return C;
}
int fakemain() {
int N, Q; cin >> N >> Q;
vector<int> X(N), Y(N);
for(int i = 0; i < N; i++) cin >> X[i];
for(int i = 0; i < N; i++) cin >> Y[i];
init(N, Q, X, Y);
for(int i = 0; i < Q; i++) {
int L, R; cin >> L >> R;
cout << max_prize(L, R) << '\n';
}
}
