#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 5e4 + 10, LOG = 16;
ll n, m, q;
ll a[N], b[N];
ll sta[N][LOG], stb[N][LOG];
ll L[N], R[N], U[N], D[N];
map<pair<ll, ll>, ll> dp;
ll geta(ll l, ll r) {
ll len = r - l + 1;
ll bit = 31 - __builtin_clz(len);
return max(sta[l][bit], sta[r - (1 << bit) + 1][bit]);
}
ll getb(ll l, ll r) {
ll len = r - l + 1;
ll bit = 31 - __builtin_clz(len);
return max(stb[l][bit], stb[r - (1 << bit) + 1][bit]);
}
ll findL(ll x, ll y) {
ll l = 0, r = y - 1;
ll ans = l;
while(l <= r) {
ll mid = (l + r) / 2;
if(getb(mid, y - 1) > a[x]) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
return ans;
}
ll findR(ll x, ll y) {
ll l = y + 1, r = m + 1;
ll ans = r;
while(l <= r) {
ll mid = (l + r) / 2;
if(getb(y + 1, mid) > a[x]) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
return ans;
}
ll findU(ll x, ll y) {
ll l = 0, r = x - 1;
ll ans = l;
while(l <= r) {
ll mid = (l + r) / 2;
if(geta(mid, x - 1) > b[y]) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
return ans;
}
ll findD(ll x, ll y) {
ll l = x + 1, r = n + 1;
ll ans = r;
while(l <= r) {
ll mid = (l + r) / 2;
if(geta(x + 1, mid) > b[y]) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
return ans;
}
ll add(ll x, ll y) {
if(x == 0 || x == n + 1 || y == 0 || y == m + 1) return 0;
if(dp[{x, y}] != 0) return dp[{x, y}];
if(a[x] < b[y]) {
ll U = findU(x, y);
ll D = findD(x, y);
dp[{x, y}] = max(dp[{x, y}], add(U, y) + x - U);
dp[{x, y}] = max(dp[{x, y}], add(D, y) + D - x);
} else {
ll L = findL(x, y);
ll R = findR(x, y);
dp[{x, y}] = max(dp[{x, y}], add(x, L) + y - L);
dp[{x, y}] = max(dp[{x, y}], add(x, R) + R - y);
}
if(dp[{x, y}] == 0) dp[{x, y}] = 1;
return dp[{x, y}];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
for(ll i = 1; i <= n; i++) {
cin >> a[i];
sta[i][0] = a[i];
}
for(ll i = 1; i <= m; i++) {
cin >> b[i];
stb[i][0] = b[i];
}
for(ll j = 1; j < LOG; j++) {
for(ll i = 0; i + (1 << (j - 1)) <= n; i++) {
sta[i][j] = max(sta[i][j - 1], sta[i + (1 << (j - 1))][j - 1]);
}
}
for(ll j = 1; j < LOG; j++) {
for(ll i = 0; i + (1 << (j - 1)) <= m; i++) {
stb[i][j] = max(stb[i][j - 1], stb[i + (1 << (j - 1))][j - 1]);
}
}
while(q--) {
ll x, y;
cin >> x >> y;
ll L = findL(x, y);
ll R = findR(x, y);
ll U = findU(x, y);
ll D = findD(x, y);
ll ans = 1;
if(L == 0) ans = max(ans, y);
else {
if(dp[{x, L}] == 0) dp[{x, L}] = add(x, L);
ans = max(ans, dp[{x, L}] + y - L);
}
if(R == m + 1) ans = max(ans, m - y + 1);
else {
if(dp[{x, R}] == 0) dp[{x, R}] = add(x, R);
ans = max(ans, dp[{x, R}] + R - y);
}
if(U == 0) ans = max(ans, x);
else {
if(dp[{U, y}] == 0) dp[{U, y}] = add(U, y);
ans = max(ans, dp[{U, y}] + x - U);
}
if(L == 0) ans = max(ans, n - x + 1);
else {
if(dp[{D, y}] == 0) dp[{D, y}] = add(D, y);
ans = max(ans, dp[{D, y}] + D - x);
}
cout << ans - 1 << "\n";
}
return 0;
}
