#include <iostream>
#include <algorithm>
#include <random>
#include <climits>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <fstream>
#include "floppy.h"
#define ll long long
// #define int ll
#define endl '\n'
#define pb push_back
#define f first
#define s second
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
#define MAX INT_MAX
#define LMAX LONG_LONG_MAX
#define MIN INT_MIN
#define LMIN LONG_LONG_MIN
using namespace std;
int init_____ = []{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
template<typename T> bool mis(T &a, const T &b) { return b < a ? a = b, true : false; }
template<typename T> bool mas(T &a, const T &b) { return b > a ? a = b, true : false; }
template<typename T> bool mise(T &a, const T &b) { return b <= a ? a = b, true : false; }
template<typename T> bool mase(T &a, const T &b) { return b >= a ? a = b, true : false; }
template<typename T> T gcd(const T &a, const T &b) { return a > b ? gcd(b, a) : (a == T(0) ? b : gcd(b % a, a)); }
template<typename T> T lcm(const T &a, const T &b) { return a * b / gcd(a, b); }
// mt19937 rng(time(NULL));
// int rand(int a, int b) {
// return a + rng() % (b - a);
// }
// string floppy;
// void save_to_floppy(string &bits) {
// floppy = bits;
// }
// void read_array(int subtask_id, const vector<int> &v);
// vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b);
// int32_t main() {
// int n; cin >> n;
// vector<int> v(n); fo(i, 0, n) cin >> v[i];
// read_array(0, v);
// cout << floppy.size() << endl;
// int m; cin >> m;
// vector<int> a(m);
// vector<int> b(m);
// fo(i, 0, m) cin >> a[i] >> b[i];
// vector<int> res = solve_queries(0, n, floppy, a, b);
// for(int i : res) cout << i << ' ';
// }
pair<int, int> a[40000];
int b[40000];
const int N = 65536;
int c[N * 2];
int d[N * 2];
void read_array(int subtask_id, const vector<int> &v) {
int n = v.size();
fo(i, 0, n) a[i] = { v[i], i };
sort(a, a + n);
fo(i, 0, n) b[a[i].s] = i;
string res;
fo(i, 0, n) {
int k = 1 << 13;
fo(j, 0, 14) {
if (b[i] & k) res += '1';
else res += '0';
k >>= 1;
}
}
save_to_floppy(res);
}
pair<int, int> get_max(int i, int cl, int cr, int l, int r) {
if (l <= cl && cr <= r) return { c[i], d[i] };
int mid = (cl + cr) / 2;
pair<int, int> res = { INT_MIN, 0 };
if (cl < r && l < mid) {
pair<int, int> asd = get_max(i * 2, cl, mid, l, r);
if (asd.f > res.f) res = asd;
}
if (mid < r && l < cr) {
pair<int, int> asd = get_max(i * 2 + 1, mid, cr, l, r);
if (asd.f > res.f) res = asd;
}
return res;
}
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b) {
fill(c + N, c + N * 2, MIN);
int j = 0;
fo(i, 0, n) {
int v = 0;
fo(k, 0, 14) {
v <<= 1;
if (bits[j++] == '1') v++;
}
c[i + N] = v;
d[i + N] = i;
}
of(i, 1, N) {
if (c[i * 2] >= c[i * 2 + 1]) {
c[i] = c[i * 2];
d[i] = d[i * 2];
} else {
c[i] = c[i * 2 + 1];
d[i] = d[i * 2 + 1];
}
}
vector<int> res;
fo(i, 0, a.size()) {
res.pb(get_max(1, 0, N, a[i], b[i] + 1).s);
}
return res;
}
