#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int h, w, q;
cin >> h >> w >> q;
vector<int> a(h);
for (int i = 0; i < h; i++) {
cin >> a[i];
}
vector<int> b(w);
for (int i = 0; i < w; i++) {
cin >> b[i];
}
const int L = 20;
vector<vector<int>> maxa(h, vector<int>(L));
vector<vector<int>> maxb(w, vector<int>(L));
for (int i = 0; i < h; i++) {
maxa[i][0] = a[i];
}
for (int i = 0; i < w; i++) {
maxb[i][0] = b[i];
}
for (int j = 1; j < L; j++) {
for (int i = 0; i + (1 << j) <= h; i++) {
maxa[i][j] = max(maxa[i][j - 1], maxa[i + (1 << (j - 1))][j - 1]);
}
}
for (int j = 1; j < L; j++) {
for (int i = 0; i + (1 << j) <= w; i++) {
maxb[i][j] = max(maxb[i][j - 1], maxb[i + (1 << (j - 1))][j - 1]);
}
}
vector<int> logs(max(h, w) + 1);
for (int i = 2; i <= max(h, w); i++) {
logs[i] = logs[i >> 1] + 1;
}
auto MaxA = [&](int L, int R) {
int k = logs[R - L + 1];
return max(maxa[L][k], maxa[R - (1 << k) + 1][k]);
};
auto MaxB = [&](int L, int R) {
int k = logs[R - L + 1];
return max(maxb[L][k], maxb[R - (1 << k) + 1][k]);
};
auto Go = [&](int x, int y, int dir) {
if (dir == 0) {
// up
if (x == 0) {
return make_pair(x, y);
}
x--;
{
if (MaxA(0, x) < b[y]) {
return make_pair(0, y);
}
int low = 0, high = x, pos = x;
while (low <= high) {
int mid = low + high >> 1;
if (MaxA(mid, x) >= b[y]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return make_pair(pos, y);
}
/* while (x > 0 && a[x] < b[y]) {
x -= 1;
}
return make_pair(x, y); */
}
if (dir == 1) {
// down
if (x == h - 1) {
return make_pair(x, y);
}
x += 1;
{
if (MaxA(x, h - 1) < b[y]) {
return make_pair(h - 1, y);
}
int low = x, high = h - 1, pos = h - 1;
while (low <= high) {
int mid = low + high >> 1;
if (MaxA(x, mid) >= b[y]) {
pos = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return make_pair(pos, y);
}
/* while (x + 1 < h && a[x] < b[y]) {
x += 1;
}
return make_pair(x, y); */
}
if (dir == 2) {
// left
if (y == 0) {
return make_pair(x, y);
}
y -= 1;
{
if (MaxB(0, y) < a[x]) {
return make_pair(x, 0);
}
int low = 0, high = y, pos = y;
while (low <= high) {
int mid = low + high >> 1;
if (MaxB(mid, y) >= a[x]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return make_pair(x, pos);
}
/* while (y > 0 && a[x] > b[y]) {
y -= 1;
}
return make_pair(x, y); */
}
if (dir == 3) {
// right
if (y == w - 1) {
return make_pair(x, y);
}
y += 1;
{
if (MaxB(y, w - 1) < a[x]) {
return make_pair(x, w - 1);
}
int low = y, high = w - 1, pos = y;
while (low <= high) {
int mid = low + high >> 1;
if (MaxB(y, mid) >= a[x]) {
pos = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return make_pair(x, pos);
}
/* while (y + 1 < w && a[x] > b[y]) {
y += 1;
}
return make_pair(x, y); */
}
assert(false);
return make_pair(-1, -1);
};
vector<map<int, bool>> was(4);
vector<map<int, int>> dp(4);
function<int(int, int, int)> Solve = [&](int x, int y, int dir) {
if (dir == 0) {
if (a[x] < b[y]) {
return 0;
}
}
if (dir == 1) {
if (a[x] < b[y]) {
return 0;
}
}
if (dir == 2) {
if (a[x] > b[y]) {
return 0;
}
}
if (dir == 3) {
if (a[x] > b[y]) {
return 0;
}
}
int curr = x * w + y;
if (was[dir][curr]) {
return dp[dir][curr];
}
was[dir][curr] = true;
if (dir == 0 || dir == 1) {
{
pair<int, int> nxt = Go(x, y, 2);
if (nxt.first != x || nxt.second != y) {
dp[dir][curr] = max(dp[dir][curr], Solve(nxt.first, nxt.second, 2) + abs(nxt.first - x) + abs(nxt.second - y));
}
}
{
pair<int, int> nxt = Go(x, y, 3);
if (nxt.first != x || nxt.second != y) {
dp[dir][curr] = max(dp[dir][curr], Solve(nxt.first, nxt.second, 3) + abs(nxt.first - x) + abs(nxt.second - y));
}
}
}
if (dir == 2 || dir == 3) {
{
pair<int, int> nxt = Go(x, y, 0);
if (nxt.first != x || nxt.second != y) {
dp[dir][curr] = max(dp[dir][curr], Solve(nxt.first, nxt.second, 0) + abs(nxt.first - x) + abs(nxt.second - y));
}
}
{
pair<int, int> nxt = Go(x, y, 1);
if (nxt.first != x || nxt.second != y) {
dp[dir][curr] = max(dp[dir][curr], Solve(nxt.first, nxt.second, 1) + abs(nxt.first - x) + abs(nxt.second - y));
}
}
}
return dp[dir][curr];
};
while (q--) {
int x, y;
cin >> x >> y;
--x; --y;
int res = 1;
for (int dir = 0; dir < 4; dir++) {
pair<int, int> cell = Go(x, y, dir);
int nx = cell.first;
int ny = cell.second;
if (nx != x || ny != y) {
res = max(res, Solve(nx, ny, dir) + abs(x - nx) + abs(y - ny));
}
}
cout << res << '\n';
for (int dir = 0; dir < 4; dir++) {
was[dir].clear();
dp[dir].clear();
}
}
return 0;
}
