#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 5e4 + 5, LG = 16;
int n, m, q;
int a[N], b[N], spt[2][LG][N], lg[N];
map<int, long long> mp[2][N];
void bld(int spt[LG][N], int *A, int n) {
for (int i = 1; i <= n; ++i) {
spt[0][i] = A[i];
}
for (int j = 1; j <= lg[n]; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
spt[j][i] = max(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
}
}
}
int qry(int spt[LG][N], int l, int r) {
int k = lg[r - l + 1];
return max(spt[k][l], spt[k][r - (1 << k) + 1]);
}
int prv(int spt[LG][N], int i, int x) {
int l = 1, r = i - 1, res = 0;
while (l <= r) {
int md = (l + r) / 2;
if (qry(spt, md, i - 1) > x) {
res = md;
l = md + 1;
} else {
r = md - 1;
}
}
return res;
}
int nxt(int spt[LG][N], int i, int n, int x) {
int l = i + 1, r = n, res = n + 1;
while (l <= r) {
int md = (l + r) / 2;
if (qry(spt, i + 1, md) > x) {
res = md;
r = md - 1;
} else {
l = md + 1;
}
}
return res;
}
long long solve(int i, int j, int dr) {
if (mp[dr][i].count(j)) {
return mp[dr][i][j];
}
long long res = 0;
if (dr == 0) {
int lt = prv(spt[1], j, a[i]), rt = nxt(spt[1], j, m, a[i]);
res = max({res, lt == 0 ? j - 1 : solve(i, lt, 1) + j - lt, rt == m + 1 ? m - j : solve(i, rt, 1) + rt - j});
} else {
int lt = prv(spt[0], i, b[j]), rt = nxt(spt[0], i, n, b[j]);
res = max({res, lt == 0 ? i - 1 : solve(lt, j, 0) + i - lt, rt == n + 1 ? n - i : solve(rt, j, 0) + rt - i});
}
return mp[dr][i][j] = res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> q;
for (int i = 2; i <= max(n, m); ++i) {
lg[i] = lg[i / 2] + 1;
}
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= m; ++i) {
cin >> b[i];
}
bld(spt[0], a, n);
bld(spt[1], b, m);
while (q--) {
int s, t; cin >> s >> t;
cout << max(solve(s, t, 0), solve(s, t, 1)) << "\n";
}
return 0;
}
