#include <stdio.h>
#include <map>
static inline int min(int a, int b) {
return a < b ? a : b;
}
static inline int max(int a, int b) {
return a > b ? a : b;
}
#define MAXN 50000
#define LOGN 16
#define VERTICAL 0
#define ORIZONTAL 1
int n, m, a[LOGN][MAXN], b[LOGN][MAXN], lg2[MAXN + 1];
std::map<long long, long long> memo;
long long solve(int l, int c, int stare) {
int i, sus, jos, st, dr;
long long ans;
if(l < 0 || c < 0 || l >= n || c >= m) {
return -1;
}
if(memo.count((1LL * l * m + c) * 2 + stare)) {
return memo[(1LL * l * m + c) * 2 + stare];
}
ans = 0;
if(stare == VERTICAL) {
sus = l - 1;
jos = l + 1;
for(i = LOGN - 1; i >= 0; i--) {
if(sus - (1 << i) + 1 >= 0 && a[i][sus - (1 << i) + 1]
<= b[0][c]) {
sus -= 1 << i;
}
if(jos + (1 << i) - 1 < n && a[i][jos] <= b[0][c]) {
jos += 1 << i;
}
}
ans = max(ans, solve(sus, c, ORIZONTAL) + l - sus);
ans = max(ans, solve(jos, c, ORIZONTAL) + jos - l);
} else {
st = c - 1;
dr = c + 1;
for(i = LOGN - 1; i >= 0; i--) {
if(st - (1 << i) + 1 >= 0 && b[i][st - (1 << i) + 1]
<= a[0][l]) {
st -= 1 << i;
}
if(dr + (1 << i) - 1 < m && b[i][dr] <= a[0][l]) {
dr += 1 << i;
}
}
ans = max(ans, solve(l, st, VERTICAL) + c - st);
ans = max(ans, solve(l, dr, VERTICAL) + dr - c);
}
return memo[(1LL * l * m + c) * 2 + stare] = ans;
}
int main() {
int q, i, j;
scanf("%d%d%d", &n, &m, &q);
for(i = 0; i < n; i++) {
scanf("%d", &a[0][i]);
}
for(i = 0; i < m; i++) {
scanf("%d", &b[0][i]);
}
for(i = 2; i <= MAXN; i++) {
lg2[i] = 1 + lg2[i >> 1];
}
for(i = 1; i <= lg2[n]; i++) {
for(j = 0; j + (1 << i) <= n; j++) {
a[i][j] = max(a[i - 1][j], a[i - 1][j + (1 << (i - 1))]);
}
}
for(i = 1; i <= lg2[m]; i++) {
for(j = 0; j + (1 << i) <= m; j++) {
b[i][j] = max(b[i - 1][j], b[i - 1][j + (1 << (i - 1))]);
}
}
while(q--) {
scanf("%d%d", &i, &j);
i--;
j--;
printf("%d\n", max(solve(i, j, VERTICAL),
solve(i, j, ORIZONTAL)));
}
return 0;
}
