#include <bits/stdc++.h>
using namespace std;
int h , w , q;
const int H = 5e4 + 5;
unordered_map<int , int> dp[2][H + 1];
int a[H + 1] , b[H + 1];
int sp[2][H+1][20];
int lg[H+1];
// 0 : --
// 1 : |
void build(int dir,int n){
for(int i = 0; i < n; i++){
sp[dir][i][0]= (dir==0 ? a[i] : b[i]);
}
for(int i=1 ; i < 18 ; i++){
for(int j=0;j + (1<<i) <= n;j++){
sp[dir][j][i]=max(sp[dir][j][i-1], sp[dir][j+(1<<(i-1))][i-1]);
}
}
}
int query(int dir,int l,int r){
if(l > r)
return -1;
int d = lg[r-l+1];
return max(sp[dir][l][d], sp[dir][r-(1<<d)+1][d]);
}
int dfs(int i , int j , int dir)
{
if(dp[dir][i].find(j) != dp[dir][i].end())
{
return dp[dir][i][j];
}
if(dir == 0)
{
int val=a[i];
int lo = j , hi = w;
while(lo + 1 < hi)
{
int md = (lo + hi)/2;
if(query(1 , j+1 , md) <= val) lo = md;
else hi = md;
}
int k = min(lo + 1 , w );
lo = -1 , hi = j;
while(lo + 1 < hi)
{
int md = (lo + hi)/2;
if(query(1 , md , j - 1) <= val)
{
hi = md;
}
else
lo = md;
}
hi--;
int k_ = max(-1 , hi);
assert(k != j && k_ != j);
if(b[k] > val)
{
dp[dir][i][j] = dfs(i , k , dir^1) + k - j;
}
else
{
dp[dir][i][j] = k - j;
}
if(k_ != -1 &&b[k_] > val){
dp[dir][i][j]= max (dp[dir][i][j] , dfs(i,k_,dir^1) + j - k_);
}
else
{
dp[dir][i][j]= max( dp[dir][i][j] , j - k_ );
}
}
else
{
int val=b[j];
int lo = i , hi = h;
while(lo + 1 < hi)
{
int md = (lo + hi)/2;
if(query(0 , i + 1 , md) <= val)
{
lo = md;
}
else
hi = md;
}
int k = min(lo + 1 , h);
lo = -1 , hi = i;
while(lo + 1 < hi)
{
int md = (lo + hi)/2;
if(query(0 , md , i - 1) <= val)
{
hi = md;
}
else
lo = md;
}
hi--;
int k_ = max(-1 , hi);
if(a[k] > val)
{
dp[dir][i][j] = dfs(k , j , dir^1) + k - i;
}
else
{
dp[dir][i][j] = k - i;
}
if(k_ != -1&&a[k_] > val){
dp[dir][i][j]= max (dp[dir][i][j] , dfs(k_,j,dir^1) + i - k_);
}
else
{
dp[dir][i][j] = max(dp[dir][i][j] , i - k_);
}
}
return dp[dir][i][j];
}
//a[i=3] = 5: - - |b[j=3]=7 - - |b[j=8]=19 - - : 7 , 19 N
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>h>>w>>q;
lg[1]=0;
for(int i=2;i<H+1;i++){
lg[i]=lg[i/2]+1;
}
for (int i=0; i<h; i++) {
cin>>a[i];
}
for (int i=0; i<w; i++) {
cin>>b[i];
}
build(0,h);
build(1,w);
while(q--){
for(int dir = 0 ; dir < 2 ; dir++)
{
for(int i = 0 ; i <= H ;i++)
{
dp[dir][i].clear();
}
}
int x,y;
cin>>x>>y;
x--;y--;
cout << max(dfs(x,y,0),dfs(x,y,1))-1 <<'\n';
}
}
