#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(161);
struct Node {
int val, priority, sz, maxVal;
int left, right;
Node() {
left = right = -1;
}
Node(int _val) {
val = _val, sz = 1, maxVal = val;
priority = rnd();
left = right = -1;
}
};
const int maxn = 2e5;
Node treap[maxn];
int getSz(int root) {
if (root == -1) { return 0; }
return treap[root].sz;
}
int getMax(int root) {
if (root == -1) { return 0; }
return treap[root].maxVal;
}
void update(int root) {
if (root == -1) { return; }
treap[root].sz = getSz(treap[root].left) + getSz(treap[root].right) + 1;
treap[root].maxVal = max(max(getMax(treap[root].left), getMax(treap[root].right)), treap[root].val);
}
int merge(int l, int r) {
if (l == -1) { return r; }
if (r == -1) { return l; }
if (treap[l].priority > treap[r].priority) {
treap[l].right = merge(treap[l].right, r);
update(l);
return l;
}
treap[r].left = merge(l, treap[r].left);
update(r);
return r;
}
pair<int, int> split(int root, int k) {
if (root == -1) { return {-1, -1}; }
int lsz = getSz(treap[root].left);
if (lsz >= k) {
auto [l, r] = split(treap[root].left, k);
treap[root].left = r;
update(root);
return {l, root};
}
auto [l, r] = split(treap[root].right, k - lsz - 1);
treap[root].right = l;
update(root);
return {root, r};
}
int getKth(int root, int k) {
if (root == -1) { return 0; }
while (root != -1) {
int lsz = getSz(treap[root].left);
if (lsz >= k) {
root = treap[root].left;
} else {
k -= lsz;
if (k == 1) {
break;
}
--k;
root = treap[root].right;
}
}
assert(root != -1);
return treap[root].val;
}
int getFirstGreater(int root, int x) {
if (root == -1) { return 0; }
int res = 0;
while (root != -1) {
if (getMax(treap[root].left) > x) {
root = treap[root].left;
} else {
res += getSz(treap[root].left);
if (treap[root].val > x) {
break;
}
root = treap[root].right;
++res;
}
}
return res;
}
void dfs(int root) {
if (root == -1) { return; }
dfs(treap[root].left);
cerr << treap[root].val << ' ';
dfs(treap[root].right);
}
struct Query {
int t, pos, i;
Query() {}
Query(int _t, int _pos, int _i) {
t = _t, pos = _pos, i = _i;
}
bool operator<(const Query& other) const {
return t < other.t;
}
~Query() {}
};
void solve() {
int n, q;
cin >> n >> q;
int half = n / 2, root = -1;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
treap[i] = Node(x);
root = merge(root, i);
}
/*cerr << "built:\n";
dfs(root);
cerr << '\n';*/
vector<Query> queries(q);
for (int i = 0; i < q; ++i) {
cin >> queries[i].t >> queries[i].pos;
queries[i].i = i;
}
sort(queries.begin(), queries.end());
int t = 0;
bool cycled = false;
vector<int> ans(q);
for (const Query& query : queries) {
while (!cycled && t < query.t) {
auto [lh, rh] = split(root, half);
int firstL = getKth(lh, 1), firstR = getKth(rh, 1);
if (firstR > getMax(lh)) {
cycled = true;
root = merge(lh, rh);
} else {
int turn = (firstL > firstR ? 1 : -1);
root = -1;
while (firstL != 0 && firstR != 0) {
if (turn == -1) {
// cut from left
int k = getFirstGreater(lh, firstR);
assert(k >= 1);
auto [start, fin] = split(lh, k);
root = merge(root, start);
firstL = getKth(fin, 1);
lh = fin;
} else {
// cut from right
int k = getFirstGreater(rh, firstL);
assert(k >= 1);
auto [start, fin] = split(rh, k);
root = merge(root, start);
firstR = getKth(fin, 1);
rh = fin;
}
turn = -turn;
}
if (firstL == 0) {
root = merge(root, rh);
} else {
root = merge(root, lh);
}
}
++t;
/*cerr << "t: " << t << '\n';
dfs(root);
cerr << '\n';*/
}
ans[query.i] = getKth(root, query.pos);
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
