#include <bits/stdc++.h>
using namespace std;
struct node {
int v;
int w;
};
const int N = 2010;
int n, m, q;
int a[N], b[N];
int f(int i, int j) { return (i - 1) * N + (j - 1); }
vector<node> g[N * N];
const int END = N * N - 1;
int dp[N * N];
bool mark[N * N];
int L[N][N], R[N][N], U[N][N], D[N][N];
void dfs(int u) {
mark[u] = true;
for(node v : g[u]) {
if(!mark[v.v]) dfs(v.v);
dp[u] = max(dp[u], dp[v.v] + v.w);
}
}
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];
for(int i = 1; i <= m; i++) cin >> b[i];
for(int i = 1; i <= n; i++) {
int lst = 0;
for(int j = 1; j <= m; j++) {
L[i][j] = lst;
if(a[i] < b[j]) lst = j;
}
lst = m + 1;
for(int j = m; j >= 1; j--) {
R[i][j] = lst;
if(a[i] < b[j]) lst = j;
}
}
for(int j = 1; j <= m; j++) {
int lst = 0;
for(int i = 1; i <= n; i++) {
U[i][j] = lst;
if(a[i] > b[j]) lst = i;
}
lst = n + 1;
for(int i = n; i >= 1; i--) {
D[i][j] = lst;
if(a[i] > b[j]) lst = i;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(a[i] < b[j]) {
if(U[i][j] != 0) g[f(i, j)].push_back({f(U[i][j], j), i - U[i][j]});
else g[f(i, j)].push_back({END, i - 1});
if(D[i][j] != n + 1) g[f(i, j)].push_back({f(D[i][j], j), D[i][j] - i});
else g[f(i, j)].push_back({END, n - i});
} else {
if(L[i][j] != 0) g[f(i, j)].push_back({f(i, L[i][j]), j - L[i][j]});
else g[f(i, j)].push_back({END, j - 1});
if(R[i][j] != m + 1) g[f(i, j)].push_back({f(i, R[i][j]), R[i][j] - j});
else g[f(i, j)].push_back({END, m - j});
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(mark[f(i, j)]) continue;
dfs(f(i, j));
}
}
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= m; j++) {
// cout << i << " " << j << ": " << dp[f(i, j)] << "\n";
// }
// }
while(q--) {
int x, y;
cin >> x >> y;
int ans = 0;
ans = max(ans, (L[x][y] == 0 ? -1 : dp[f(x, L[x][y])]) + y - L[x][y]);
ans = max(ans, (R[x][y] == m + 1 ? -1 : dp[f(x, R[x][y])]) + R[x][y] - y);
ans = max(ans, (U[x][y] == 0 ? -1 : dp[f(U[x][y], y)]) + x - U[x][y]);
ans = max(ans, (D[x][y] == n + 1 ? -1 : dp[f(D[x][y], y)]) + D[x][y] - x);
cout << ans << "\n";
}
return 0;
}
