#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using namespace std;
struct node
{
int r, c, i;
};
const int mx = 50'000;
vi A(1+mx), B(1+mx);
const ll inf = 1'000'000'000'000'000LL;
int congestion(int i)
{
if(i > 0)
return A[i];
else
return B[-i];
}
struct inedge
{
int i; //index
int c; //congestion
ll d; //dp
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int H, W, Q;
cin >> H >> W >> Q;
for(int i = 1; i <= H; i++)
cin >> A[i];
for(int j = 1; j <= W; j++)
cin >> B[j];
vi roads;
for(int i = 1; i <= H; i++)
roads.push_back(i);
for(int j = 1; j <= W; j++)
roads.push_back(-j);
sort(roads.begin(), roads.end(), [] (int p, int q)
{
return congestion(p) < congestion(q);
});
A[0] = B[0] = 0;
for(int q = 1; q <= Q; q++)
{
int S, T;
cin >> S >> T;
ll res = 0;
// vll horiz_left(1+H, -inf), horiz_center(1+H, -inf), horiz_right(1+H, -inf); //dp
// vll vert_up(1+W, -inf), vert_center(1+W, -inf), vert_down(1+W, -inf);
ll ui = S-1, di = S+1, li = T-1, ri = T+1;
vector<inedge> horiz_in[1+H], vert_in[1+W];
horiz_in[S].push_back({T, 0, 0});
vert_in[T].push_back({S, 0, 0});
for(int f : roads)
{
if(f > 0) //road is horizontal
{
ll hl = -inf, hc = -inf, hr = -inf;
int z = f;
while(li >= 1 && B[li] < A[z])
li--;
while(ri <= W && B[ri] < A[z])
ri++;
for(inedge x : horiz_in[z])
{
if(x.c >= A[z]) continue;
if(x.i <= li || ri <= x.i) continue;
if(A[z] < B[T])
hc = max(hc, x.d + abs(T - x.i));
if(li != 0 && (x.i <= T || A[z] > B[T]))
{
hl = max(hl, x.d + abs(li - x.i));
}
else if(li == 0 && (x.i <= T || A[z] > B[T]))
res = max(res, x.d + abs(x.i - 1));
if(ri != W+1 && (x.i >= T || A[z] > B[T]))
{
hr = max(hr, x.d + abs(ri - x.i));
}
else if(ri == W+1 && (x.i >= T || A[z] > B[T]))
res = max(res, x.d + abs(x.i - W));
}
if(A[z] < B[T])
{
vert_in[T].push_back({z, A[z], hc});
}
if(li != 0)
vert_in[li].push_back({z, A[z], hl});
if(ri != W+1)
vert_in[ri].push_back({z, A[z], hr});
}
else
{
ll vu = -inf, vc = -inf, vd = -inf;
int z = -f;
while(ui >= 1 && A[ui] < B[z])
ui--;
while(di <= H && A[di] < B[z])
di++;
for(inedge x : vert_in[z])
{
if(x.c >= B[z]) continue;
if(x.i <= ui || di <= x.i) continue;
if(B[z] < A[S])
vc = max(vc, x.d + abs(S - x.i));
if(ui != 0 && (x.i <= S || B[z] > A[S]))
{
vu = max(vu, x.d + abs(ui - x.i));
}
else if(ui == 0 && (x.i <= S || B[z] > A[S]))
res = max(res, x.d + abs(1 - x.i));
if(di != H+1 && (x.i >= S || B[z] > A[S]))
{
vd = max(vd, x.d + abs(di - x.i));
}
else if(di == H+1 && (x.i >= S || B[z] > A[S]))
res = max(res, x.d + abs(H - x.i));
}
if(B[z] < A[S])
{
horiz_in[S].push_back({z, B[z], vc});
}
if(ui != 0)
horiz_in[ui].push_back({z, B[z], vu});
if(di != H+1)
horiz_in[di].push_back({z, B[z], vd});
}
}
cout << res << '\n';
}
}
