#include <bits/stdc++.h>
using namespace std;
const int MAX = 50000;
const int L = 18;
int h, w, q, a[MAX], b[MAX], logs[MAX];
int maxa[MAX][L], maxb[MAX][L];
unordered_map<int, bool> was[4];
unordered_map<int, long long> dp[4];
int MaxA(int L, int R) {
int k = logs[R - L + 1];
return max(maxa[L][k], maxa[R - (1 << k) + 1][k]);
}
int MaxB(int L, int R) {
int k = logs[R - L + 1];
return max(maxb[L][k], maxb[R - (1 << k) + 1][k]);
}
pair<int, int> 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);
}
long long Solve(int x, int y, int dir) {
if (dir <= 1) {
if (a[x] < b[y]) {
return 0LL;
}
} else {
if (a[x] > b[y]) {
return 0LL;
}
}
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];
}
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]);
}
}
for (int i = 2; i <= max(h, w); i++) {
logs[i] = logs[i >> 1] + 1;
}
while (q--) {
int x, y;
cin >> x >> y;
--x; --y;
long long 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;
}
