#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
map<pair<pair<ll,ll>,ll>,ll>mem;
ll mx[50007][16][2];
ll h,w,q,a,b;
ll wlw(ll x,ll g,ll idx){
for(ll j=15;j>=0;j--){
if(g>=(1<<j) && mx[g-(1<<j)][j][idx]<x){
g=g-(1<<j);
}
}
return g-1;
}
ll wpw(ll x,ll g,ll idx){
for(ll j=15;j>=0;j--){
if(mx[g+1][j][idx]<x){
// cout<<j<<" ";
g=g+(1<<j);
}
}
return g+1;
}
ll slv(ll x,ll y,ll idx){
if(x<0 || y<0 || x>=h || y>=w)return -1;
if(mem.find({{x,y},idx})!=mem.end())return mem[{{x,y},idx}];
if(idx==0){
//cout<<"xd1"<<flush;
//cout<<mx[y][0][1]<<" 1 ";
ll lw=wlw(mx[y][0][1],x,0);
ll pw=wpw(mx[y][0][1],x,0);
mem[{{x,y},idx}]=max(slv(lw,y,!idx)+x-lw,slv(pw,y,!idx)+pw-x);
//cout<<"\n";
return mem[{{x,y},idx}];
}
else{
//cout<<"xd2"<<flush;
//cout<<mx[x][0][0]<<" 2 ";
ll lw=wlw(mx[x][0][0],y,1);
//cout<<"xd2"<<flush;
ll pw=wpw(mx[x][0][0],y,1);
//cout<<x<<" "<<y<<" "<<lw<< " "<<pw<<"\n"<<flush;
mem[{{x,y},idx}]=max(slv(x,lw,!idx)+y-lw,slv(x,pw,!idx)+pw-y);
//cout<<"\n";
return mem[{{x,y},idx}];
}
}
int main(){
cin>>h>>w>>q;
for(ll i=0;i<50007;i++)for(ll j=0;j<16;j++)for(ll k=0;k<2;k++)mx[i][j][k]=INFL;
for(ll i=0;i<h;i++){
cin>>mx[i][0][0];
}
for(ll i=0;i<w;i++){
cin>>mx[i][0][1];
}
for(ll j=1;j<16;j++){
for(ll i=0;i+(1<<j)<=h;i++){
mx[i][j][0]=max(mx[i][j-1][0],mx[i+(1<<(j-1))][j-1][0]);
//cout<<mx[i][j][0]<<" ";
}
//cout<<"\n";
for(ll i=0;i+(1<<j)<=w;i++){
mx[i][j][1]=max(mx[i][j-1][1],mx[i+(1<<(j-1))][j-1][1]);
//cout<<mx[i][j][1]<<" ";
}
//cout<<"\n\n";
}
//cout<<"xd";
//return 0;
for(ll i=0;i<q;i++){
cin>>a>>b;
cout<<max(slv(a-1,b-1,0),slv(a-1,b-1,1))<<"\n";
}
}
