#pragma GCC optimize("O2,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50000;
const int M = 16;
int n[2], q, a[2][N + 10];
ll mx[2][N + 10][M + 3];
void readInput() {
cin >> n[0] >> n[1] >> q;
for (int t = 0; t < 2; t++)
for (int i = 1; i <= n[t]; i++)
cin >> a[t][i];
}
void calcRMQ() {
for (int t = 0; t < 2; t++) {
for (int i = 1; i <= n[t]; i++)
mx[t][i][0] = a[t][i];
for (int j = 1; j <= M; j++)
for (int i = 1; i + (1 << j) - 1 <= n[t]; i++)
mx[t][i][j] = max(mx[t][i][j - 1], mx[t][i + (1 << (j - 1))][j - 1]);
}
}
int getMax(int t, int l, int r) {
int lg = 31 - __builtin_clz(r - l + 1);
return max(mx[t][l][lg], mx[t][r - (1 << lg) + 1][lg]);
}
int getLeft(int t, int i, int x) {
int l = 0, r = i;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (getMax(t, mid, i - 1) > x)
l = mid;
else
r = mid;
}
return l;
}
int getRight(int t, int i, int x) {
int l = i, r = n[t] + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (getMax(t, i + 1, mid) > x)
r = mid;
else
l = mid;
}
return r;
}
map<pair<int, pair<int, int>>, ll> mp;
ll calcDP(int t, int i, int j) {
if (mp[{t, {i, j}}])
return mp[{t, {i, j}}] - 1;
int idx[2] = {i, j};
int x = a[1 - t][idx[1 - t]];
int l = getLeft(t, idx[t], x);
int case1;
if (l == 0)
case1 = idx[t] - 1;
else {
case1 = (t == 0? calcDP(1, l, idx[1]): calcDP(0, idx[0], l));
case1 += idx[t] - l;
}
int r = getRight(t, idx[t], x);
int case2;
if (r == n[t] + 1)
case2 = r - idx[t] - 1;
else {
case2 = (t == 0? calcDP(1, r, idx[1]): calcDP(0, idx[0], r));
case2 += r - idx[t];
}
mp[{t, {i, j}}] = max(case1, case2) + 1;
return max(case1, case2);
}
void calcDP() {
vector<pair<pair<int, int>, pair<int, int>>> vec;
for (int i = 1; i <= n[0]; i++)
for (int j = 1; j <= n[1]; j++) {
vec.push_back({{a[1][j], 0}, {i, j}});
vec.push_back({{a[0][i], 1}, {i, j}});
}
sort(vec.begin(), vec.end());
for (int i = (int) vec.size() - 1; i >= 0; i--)
calcDP(vec[i].first.second, vec[i].second.first, vec[i].second.second);
}
void query() {
int x, y;
cin >> x >> y;
cout << max(calcDP(0, x, y), calcDP(1, x, y)) << '\n';
}
void solve() {
while (q--)
query();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
calcRMQ();
solve();
return 0;
}
