// Be name khoda //
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
const int maxn5 = 1e5 + 10;
const int maxnt = 4e5 + 10;
struct segment_tree{
int val[maxn5];
int mx[maxnt];
inline void build(int l, int r, int v){
if(r - l == 1){
mx[v] = val[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
inline int get_first(int l, int r, int lq, int rq, int val, int v){
if(rq <= l || r <= lq || mx[v] <= val)
return -1;
if(r - l == 1)
return l;
int mid = (l + r) >> 1;
int ans = get_first(l, mid, lq, rq, val, v * 2);
if(ans != -1)
return ans;
return get_first(mid, r, lq, rq, val, v * 2 + 1);
}
inline int get_last(int l, int r, int lq, int rq, int val, int v){
if(rq <= l || r <= lq || mx[v] <= val)
return -1;
if(r - l == 1)
return l;
int mid = (l + r) >> 1;
int ans = get_last(mid, r, lq, rq, val, v * 2 + 1);
if(ans != -1)
return ans;
return get_last(l, mid, lq, rq, val, v * 2);
}
} seg1, seg2;
int a[maxn5], b[maxn5], pt1[2][maxn5], pt2[2][maxn5];
int up[maxn5], dw[maxn5], lef[maxn5], rig[maxn5];
vector <pair<pair<int, int>, bool>> av;
ll ans[2][2][maxn5], n, m, x, y;
inline ll setmn(ll a, ll b){
if(a == -1)
return b;
if(b == -1)
return a;
return min(a, b);
}
inline ll setmx(ll a, ll b){
if(a == -1)
return b;
if(b == -1)
return a;
return max(a, b);
}
inline ll solve(bool exty){
//cout << "satring with solve " << endl;
for(auto [p, ty] : av){
int id = p.se;
if(ty && up[id] == -1)
continue;
if(!ty && lef[id] == -1)
continue;
if(ty){ // stoon
int pt = seg1.get_last(0, n, 0, up[id] + 1, b[id], 1);
if(pt != -1){
lef[pt] = setmn(lef[pt], id);
rig[pt] = setmx(rig[pt], id);
}
else{
ans[ty][0][id] = up[id];
}
pt1[ty][id] = pt;
pt = seg1.get_first(0, n, dw[id], n, b[id], 1);
if(pt != -1){
lef[pt] = setmn(lef[pt], id);
rig[pt] = setmx(rig[pt], id);
}
else{
ans[ty][1][id] = n - dw[id] - 1;
}
pt2[ty][id] = pt;
}
else{ // satr
int pt = seg2.get_last(0, m, 0, lef[id] + 1, a[id], 1);
if(pt != -1){
dw[pt] = setmx(dw[pt], id);
up[pt] = setmn(up[pt], id);
}
else{
ans[ty][0][id] = lef[id];
}
pt1[ty][id] = pt;
pt = seg2.get_first(0, m, rig[id], m, a[id], 1);
if(pt != -1){
dw[pt] = setmx(dw[pt], id);
up[pt] = setmn(up[pt], id);
}
else{
ans[ty][1][id] = m - rig[id] - 1;
}
pt2[ty][id] = pt;
}
//cout << ty << ' ' << id << ' ' << lef[id] << ' ' << rig[id] << ' ' << up[id] << ' ' << dw[id] << endl;
//cout << "edame " << pt1[ty][id] << ' ' << pt2[ty][id] << ' ' << ans[ty][0][id] << ' ' << ans[ty][1][id] << endl;
}
reverse(all(av));
for(auto [p, ty] : av){
int id = p.se;
if(ty && up[id] == -1)
continue;
if(!ty && lef[id] == -1)
continue;
int pt = pt1[ty][id];
if(pt1[ty][id] != -1){
if(ty){
ans[ty][0][id] = max(ans[ty ^ 1][0][pt] + id - lef[pt], ans[ty ^ 1][1][pt] + rig[pt] - id) + up[id] - pt;
}
else{
ans[ty][0][id] = max(ans[ty ^ 1][0][pt] + id - up[pt], ans[ty ^ 1][1][pt] + dw[pt] - id) + lef[id] - pt;
}
}
pt = pt2[ty][id];
if(pt != -1){
if(ty){
ans[ty][1][id] = max(ans[ty ^ 1][0][pt] + id - lef[pt], ans[ty ^ 1][1][pt] + rig[pt] - id) + pt - dw[id];
}
else{
ans[ty][1][id] = max(ans[ty ^ 1][0][pt] + id - up[pt], ans[ty ^ 1][1][pt] + dw[pt] - id) + pt - rig[id];
}
}
//cout << "ans of " << ty << ' '<< id << ' ' << ans[ty][0][id] << ' ' << ans[ty][1][id] << endl;
}
//cout << max({ans[0][0][x], ans[0][1][x], ans[1][0][y], ans[1][1][y]}) << '\n';
reverse(all(av));
if(exty){
ans[1][0][y] = ans[1][1][y] = (up[y] < x ? ans[1][0][y] : ans[1][1][y]);
return max({ans[0][0][x], ans[0][1][x], ans[1][0][y] + 1, ans[1][1][y] + 1});
}
else{
ans[0][0][x] = ans[0][1][x] = (lef[x] > y ? ans[0][1][x] : ans[0][0][x]);
return max({ans[0][0][x] + 1, ans[0][1][x] + 1, ans[1][0][y], ans[1][1][y]});
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q; cin >> n >> m >> q;
for(int i = 0; i < n; i++){
cin >> a[i];
seg1.val[i] = a[i];
av.pb({{a[i], i}, 0});
}
for(int i = 0; i < m; i++){
cin >> b[i];
seg2.val[i] = b[i];
av.pb({{b[i], i}, 1});
}
sort(all(av));
seg1.build(0, n, 1);
seg2.build(0, m, 1);
for(int i = 0; i < q; i++){
cin >> x >> y;
x--; y--;
ll anss = 0;
if(a[x] > b[y]){
memset(lef, -1, sizeof lef);
memset(rig, -1, sizeof rig);
memset(up, -1, sizeof up);
memset(dw, -1, sizeof dw);
memset(ans, 0, sizeof ans);
lef[x] = rig[x] = y;
up[y] = dw[y] = x - 1;
if(x > 0)
anss = max(anss, solve(true));
memset(lef, -1, sizeof lef);
memset(rig, -1, sizeof rig);
memset(up, -1, sizeof up);
memset(dw, -1, sizeof dw);
memset(ans, 0, sizeof ans);
lef[x] = rig[x] = y;
up[y] = dw[y] = x + 1;
if(x + 1 < n)
anss = max(anss, solve(true));
}
else{
memset(lef, -1, sizeof lef);
memset(rig, -1, sizeof rig);
memset(up, -1, sizeof up);
memset(dw, -1, sizeof dw);
memset(ans, 0, sizeof ans);
up[y] = dw[y] = x;
lef[x] = rig[x] = y - 1;
if(y > 0)
anss = max(anss, solve(false));
memset(lef, -1, sizeof lef);
memset(rig, -1, sizeof rig);
memset(up, -1, sizeof up);
memset(dw, -1, sizeof dw);
memset(ans, 0, sizeof ans);
up[y] = dw[y] = x;
lef[x] = rig[x] = y + 1;
if(y + 1 < m)
anss = max(anss, solve(false));
}
cout << anss << '\n';
}
}
/*
3 3 1
3 2 6
1 4 5
3 3
*/
