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