#include <bits/stdc++.h>
using i64 = long long;
constexpr int Log = 16;
constexpr int N = 50000;
int am[Log][N], bm[Log][N];
void chmax(i64 &a, i64 b) {
if (a < b)
a = b;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, q;
std::cin >> n >> m >> q;
std::vector<int> a(n), b(m);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
for (int i = 0; i < m; i++) {
std::cin >> b[i];
}
for (int i = 0; i < n; i++)
am[0][i] = a[i];
for (int j = 0; (1 << (j + 1)) <= n; j++)
for (int i = 0; i + (1 << (j + 1)) <= n; i++)
am[j + 1][i] = std::max(am[j][i], am[j][i + (1 << j)]);
for (int i = 0; i < m; i++)
bm[0][i] = b[i];
for (int j = 0; (1 << (j + 1)) <= m; j++)
for (int i = 0; i + (1 << (j + 1)) <= m; i++)
bm[j + 1][i] = std::max(bm[j][i], bm[j][i + (1 << j)]);
std::unordered_map<i64, i64> dp;
std::function<i64(int, int, int)> calc = [&](int x, int y, int t) {
i64 state = x * 1LL * m + y + t * (1LL << 60);
if (dp.count(state))
return dp[state];
i64 res = 0;
if (t == 0) {
int j = y + 1;
for (int k = Log - 1; k >= 0; k--)
if (j + (1 << k) <= m && bm[k][j] <= a[x])
j += 1 << k;
if (j == m)
chmax(res, m - 1 - y);
else
chmax(res, j - y + calc(x, j, !t));
j = y;
for (int k = Log - 1; k >= 0; k--)
if (j - (1 << k) >= 0 && bm[k][j - (1 << k)] <= a[x])
j -= 1 << k;
j--;
if (j == -1)
chmax(res, y);
else
chmax(res, y - j + calc(x, j, !t));
} else {
int i = x + 1;
for (int k = Log - 1; k >= 0; k--)
if (i + (1 << k) <= n && am[k][i] <= b[y])
i += 1 << k;
if (i == n)
chmax(res, n - 1 - x);
else
chmax(res, i - x + calc(i, y, !t));
i = x;
for (int k = Log - 1; k >= 0; k--)
if (i - (1 << k) >= 0 && am[k][i - (1 << k)] <= b[y])
i -= 1 << k;
i--;
if (i == -1)
chmax(res, x);
else
chmax(res, x - i + calc(i, y, !t));
}
return dp[state] = res;
};
while (q--) {
int s, t;
std::cin >> s >> t;
s--;
t--;
std::cout << std::max(calc(s, t, 0), calc(s, t, 1)) << "\n";
}
return 0;
}
