#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".txt").c_str(),"r",stdin);
// freopen((name+".out").c_str(),"w",stdout);
}
int aa[50001];
int bb[50001];
int n,m,q;
vector<pair<pair<int,int>,int>> ss;
//set<pair<int,int>> xx[2];
llo dp[100001][2];
int ind5[50001][2];
vector<pair<int,int>> yy[2];
vector<pair<int,int>> zz[2];
int coo=0;
llo solve(int i,int j){
//cout<<i<<",,"<<j<<endl;
int ind=-1;
int ind2=-1;
for(int ii=0;ii<ss.size();ii++){
if(ss[ii].a.b==i and ss[ii].b==0){
ind=ii;
}
if(ss[ii].a.b==j and ss[ii].b==1){
ind2=ii;
}
}
//xx[0].clear();
//xx[1].clear();
pair<pair<int,int>,int> cur={{i,i},0};
pair<pair<int,int>,int> cur2={{j,j},1};
//vector<pair<int,int>> kk2;
//vector<pair<int,int>> kk3;
yy[0].clear();
yy[1].clear();
zz[0].clear();
zz[1].clear();
for(int x=0;x<i;x++){
if(aa[x]>aa[i]){
yy[0].pb({x,ind5[x][0]});
}
}
for(int x=n-1;x>i;x--){
if(aa[x]>aa[i]){
zz[0].pb({x,ind5[x][0]});
}
}
for(int x=0;x<j;x++){
if(bb[x]>bb[j]){
yy[1].pb({x,ind5[x][1]});
}
}
for(int x=m-1;x>j;x--){
if(bb[x]>bb[j]){
zz[1].pb({x,ind5[x][1]});
}
}
/*for(int jj=max(ind,ind2)+1;jj<ss.size();jj++){
if(ss[jj].b==0){
xx[0].insert({ss[jj].a.b,jj});
}
else{
xx[1].insert({ss[jj].a.b,jj});
}
coo++;
}
*/ //xx[0]={kk2};
//set<llo> yy(kk2.begin(),kk2.end());
//return 0;
//cout<<ind<<":::"<<ind2<<endl;
int ok=0;
if(ind>ind2){
ok=1;
swap(cur,cur2);
swap(ind,ind2);
}
int l=ind2;
vector<pair<int,int>> ans;
vector<pair<int,int>> ans2;
ans.pb({cur.a.a,cur.a.b});
ans2.pb({ind,ind});
ans.pb({cur2.a.a,cur2.a.b});
ans2.pb({ind2,ind2});
//cout<<cur.b<<"::"<<cur2.b<<endl;
/*int ka=0;
if(i==1820 and j==1935){
ka=1;
}*/
dp[0][0]=0;
dp[0][1]=0;
dp[1][0]=0;
dp[1][1]=0;
llo ma=0;
while(true){
/* for(auto j:ans){
cout<<j.a<<","<<j.b<<endl;
}
cout<<endl;*/
int xi=2;
if(ans.size()>=7){
xi=ans.size()-3;
}
for(int i=xi;i<ans.size();i++){
dp[i][0]=max(dp[i-2][0]+abs(ans[i-2].a-ans[i].a),dp[i-2][1]+abs(ans[i-2].b-ans[i].a));
dp[i][1]=max(dp[i-2][0]+abs(ans[i-2].a-ans[i].b),dp[i-2][1]+abs(ans[i-2].b-ans[i].b));
}
/*if(ans.size()==4){
cout<<dp[]
}*/
// assert(cur.b-cur2.b==1);
// cout<<cur.b<<",,"<<cur2.b<<","<<(ans.size()%2)<<endl;
pair<int,int> le={-1,-1};//pos in original,pos in ss
pair<int,int> re={-1,-1};
while(yy[cur.b].size()){
if(yy[cur.b].back().b<=l){
yy[cur.b].pop_back();
}
else{
le=yy[cur.b].back();
break;
}
}
while(zz[cur.b].size()){
if(zz[cur.b].back().b<=l){
zz[cur.b].pop_back();
}
else{
re=zz[cur.b].back();
break;
}
}
/*while(l<min(ans2.back().a,ans2.back().b)){
int jj=l+1;
xx[ss[jj].b].erase({ss[jj].a.b,jj});
l++;
}*/
l=min(ans2.back().a,ans2.back().b);
/*auto j=xx[cur.b].lower_bound({max(cur.a.b,cur.a.a)+1,-1});
if(j!=xx[cur.b].end()){
re=(*j);
}
if(j!=xx[cur.b].begin()){
j--;
le=(*j);
}*/
/*auto jj=xx[cur.b].lower_bound({min(cur.a.a,cur.a.b),-1});
if(jj!=xx[cur.b].begin()){
jj--;
le=(*jj);
}*/
/* if(cur.a.a==1936){
cout<<le.a<<"<"<<le.b<<endl;
}*/
if(le.a==-1 and re.a==-1){
llo cot=max(dp[ans.size()-1][0],dp[ans.size()-1][1]);
int pa=n-1;
if(cur.b==1){
pa=m-1;
}
cot+=max(dp[ans.size()-2][0]+max(cur.a.a,pa-cur.a.a),dp[ans.size()-2][1]+max(cur.a.b,pa-cur.a.b));
ma=max(ma,cot);
/* for(auto j:ans){
cout<<j.a<<",,"<<j.b<<endl;
}
cout<<cot<<endl;*/
break;
}
if(le.a==-1){
swap(le,re);
}
else if(re.a==-1){
}
else{
if(le.b>re.b){
swap(le,re);
}
}
/*if(ans.size()==3){
cout<<le.a<<":"<<le.b<<":"<<re.a<<":"<<re.b<<endl;
}*/
if(le.b>=0 and le.b<max(ans2.back().a,ans2.back().b)){
pair<int,int> za=ans.back();
pair<int,int> za2=ans2.back();
/* cout<<za2.a<<","<<za2.b<<endl;
cout<<le.b<<endl;
cout<<ans2.size()<<"?"<<endl;*/
ans.pop_back();;
ans2.pop_back();
if(le.b<za2.a){
//assert(le.b>za2.b);
ans.pb({za.b,za.b});
ans2.pb({za2.b,za2.b});
ans.pb({le.a,le.a});
ans2.pb({le.b,le.b});
ans.pb({za.a,za.a});
ans2.pb({za2.a,za2.a});
}
else{
// assert(le.b>za2.a);
ans.pb({za.a,za.a});
ans2.pb({za2.a,za2.a});
ans.pb({le.a,le.a});
ans2.pb({le.b,le.b});
ans.pb({za.b,za.b});
ans2.pb({za2.b,za2.b});
}
if(le.a<cur.a.a){
yy[cur.b].pop_back();
}
else{
zz[cur.b].pop_back();
}
//assert(n<=20);
/* cout<<11<<endl;
for(int i=0;i<5;i++){
if(ans.size()>=i+1){
cout<<ans2[ans2.size()-i-1].a<<"::"<<ans2[ans2.size()-i-1].b<<endl;
}
}*/
/* for(int jj=l+1;jj<=ans2.back().a;jj++){
xx[ss[jj].b].erase({ss[jj].a.b,jj});
}*/
l=ans2.back().a;
int zaa=cur.b;
cur={ans[ans.size()-2],zaa};
cur2={ans.back(),1-zaa};
continue;
}
else{
/* for(int jj=l+1;jj<=max(ans2.back().b,ans2.back().a);jj++){
xx[ss[jj].b].erase({ss[jj].a.b,jj});
}
l=max(ans2.back().b,ans2.back().a);*/
l=max(ans2.back().a,ans2.back().b);
}
if(re.a==-1){
llo cot=max(dp[ans.size()-1][0],dp[ans.size()-1][1]);
if(le.a>max(cur.a.b,cur.a.a)){
cot+=max(dp[ans.size()-2][0]+cur.a.a,dp[ans.size()-2][1]+cur.a.b);
}
else{
//cout<<33<<endl;
int pa=n-1;
if(cur.b==1){
pa=m-1;
}
//cout<<pa<<",,,,"<<endl;
cot+=max(dp[ans.size()-2][0]+abs(pa-cur.a.a),dp[ans.size()-2][1]+abs(pa-cur.a.b));
}
//cout<<cot<<":::"<<endl;
ma=max(ma,cot);
ans.pb({le.a,le.a});
ans2.pb({le.b,le.b});
if(le.a<cur.a.a){
yy[cur.b].pop_back();
}
else{
zz[cur.b].pop_back();
}
pair<pair<int,int>,int> cur3={{le.a,le.a},cur.b};
/*for(int jj=l+1;jj<=le.b;jj++){
xx[ss[jj].b].erase({ss[jj].a.b,jj});
}
l=le.b;*/
l=le.b;
cur=cur2;
cur2=cur3;
continue;
}
/*if(le.b>re.b){
swap(le,re);
}*/
/*for(int jj=l+1;jj<=le.b;jj++){
xx[ss[jj].b].erase({ss[jj].a.b,jj});
}
l=le.b;*/
l=le.b;
pair<int,int> cc={-1,-1};
pair<int,int> dd={-1,-1};
while(yy[cur2.b].size()){
if(yy[cur2.b].back().b<=l){
yy[cur2.b].pop_back();
}
else{
cc=yy[cur2.b].back();
break;
}
}
while(zz[cur2.b].size()){
if(zz[cur2.b].back().b<=l){
zz[cur2.b].pop_back();
}
else{
dd=zz[cur2.b].back();
break;
}
}
/* auto pp=xx[cur2.b].lower_bound({max(cur2.a.b,cur2.a.a)+1,-1});
if(pp!=xx[cur2.b].end()){
cc=*pp;
}
if(pp!=xx[cur2.b].begin()){
pp--;
dd=(*pp);
} */
if((cc.b>le.b and cc.b<re.b) or (dd.b>le.b and dd.b<re.b)){
ans.pb({le.a,le.a});
ans2.pb({le.b,le.b});
if(le.a<cur.a.a){
yy[cur.b].pop_back();
}
else{
zz[cur.b].pop_back();
}
pair<pair<int,int>,int> cur3={{le.a,le.a},cur.b};
cur=cur2;
cur2=cur3;
continue;
}
else{
ans.pb({min(le.a,re.a),max(le.a,re.a)});
if(le.a<re.a){
ans2.pb({le.b,re.b});
}
else{
ans2.pb({re.b,le.b});
}
yy[cur.b].pop_back();
zz[cur.b].pop_back();
l=re.b;
pair<pair<int,int>,int> cur3={{min(le.a,re.a),max(le.a,re.a)},cur.b};
cur=cur2;
cur2=cur3;
continue;
}
}
/* for(auto j:ans){
cout<<j.a<<":"<<j.b<<endl;
}*/
return ma;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//setIO("05-12");
cin>>n>>m>>q;
for(int i=0;i<n;i++){
cin>>aa[i];
ss.pb({{aa[i],i},0});
}
for(int i=0;i<m;i++){
cin>>bb[i];
ss.pb({{bb[i],i},1});
}
sort(ss.begin(),ss.end());
for(int i=0;i<ss.size();i++){
ind5[ss[i].a.b][ss[i].b]=i;
}
while(q--){
llo l,r;
cin>>l>>r;
l--;
r--;
llo ans=0;
for(int x=l-1;x>=0;x--){
if(aa[x]>bb[r]){
ans=max(ans,solve(x,r)+(l-x));
break;
}
ans=max(ans,abs(x-l));
}
for(int x=l+1;x<n;x++){
if(aa[x]>bb[r]){
ans=max(ans,solve(x,r)+abs(l-x));
break;
}
ans=max(ans,abs(x-l));
}
for(int x=r-1;x>=0;x--){
if(bb[x]>aa[l]){
ans=max(ans,solve(l,x)+abs(x-r));
break;
}
ans=max(ans,abs(x-r));
}
for(int x=r+1;x<m;x++){
if(bb[x]>aa[l]){
ans=max(ans,solve(l,x)+abs(x-r));
break;
}
ans=max(ans,abs(x-r));
}
cout<<ans<<endl;
}
//cout<<coo<<endl;
//int x=2e9;
////x+=5e8;
//cout<<x<<endl;
return 0;
}
