#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LOG = 31;
const int MAX_N = 200000;
template <typename T>
using vc = vector<T>;
struct WM {
int C[LOG][MAX_N + 1];
ll S[LOG][MAX_N + 1];
int zero[LOG];
void build(vc<int> A) {
int n = A.size();
for (int d = LOG - 1; d >= 0; --d) {
vc<int> L, R;
C[d][0] = 0;
for (int i = 0; i < n; ++i) {
int x = A[i];
C[d][i + 1] = C[d][i] + (x >> d & 1);
((x >> d & 1) ? R : L).emplace_back(x);
}
zero[d] = L.size();
for (int i = 0; i < int(L.size()); ++i) A[i] = L[i];
for (int i = 0; i < int(R.size()); ++i) A[zero[d] + i] = R[i];
S[d][0] = 0;
for (int i = 0; i < n; ++i) S[d][i + 1] = S[d][i] + A[i];
}
}
ll solve(int L, int R) {
ll all_cnt = R - L;
ll n = all_cnt / 2;
ll cnt = 0, sm = 0;
ll ans = 0;
for (int d = LOG - 1; d >= 0; --d) {
ll K = ans + (1LL << d);
int L0 = L - C[d][L];
int R0 = R - C[d][R];
int L1 = zero[d] + C[d][L];
int R1 = zero[d] + C[d][R];
// lhs := sum_i min(A_i,K)
// rhs := n(K)/2
ll lhs = sm + (S[d][R0] - S[d][L0]) + K * (all_cnt - cnt - (R0 - L0));
ll rhs = n * K;
if (lhs >= rhs) {
ans = K;
cnt = cnt + (R0 - L0);
sm = sm + (S[d][R0] - S[d][L0]);
L = L1, R = R1;
} else {
L = L0, R = R0;
}
}
return ans;
}
};
struct RMQ {
int n;
vc<int> dat;
void build(vc<int> A) {
n = A.size();
dat.resize(2 * n);
for (int i = 0; i < n; ++i) dat[n + i] = A[i];
for (int i = n - 1; i >= 1; --i) dat[i] = min(dat[2 * i + 0], dat[2 * i + 1]);
}
ll solve(int L, int R) {
int ans = 2e9;
L += n, R += n;
while (L < R) {
if (L & 1) ans = min(ans, dat[L++]);
if (R & 1) ans = min(ans, dat[--R]);
L /= 2, R /= 2;
}
return ans;
}
};
RMQ seg;
WM WMX, WMY;
void init(int N, int Q, vc<int> X, vc<int> Y) {
vc<int> Z(N);
for (int i = 0; i < N; ++i) Z[i] = X[i] + Y[i];
seg.build(Z);
WMX.build(X);
WMY.build(Y);
}
int max_prize(int L, int R) {
++R;
ll ans = 2e9;
ans = min(ans, seg.solve(L, R));
ans = min(ans, WMX.solve(L, R));
ans = min(ans, WMY.solve(L, R));
return ans;
}
