Problem: Problem

Phantom thief Rappan came to steal the jewels. It was easy to get the jewel, but the jewel was equipped with a sensor and was surrounded by security robots.

The guard robot is designed to move towards the jewel. The sensor didn't seem to be easy to remove, so I decided to put a jewel and escape. I decided to keep the jewels as far away from the guard robot as possible to give me time to escape.

The site has a rectangular shape consisting of n x m squares and there are no obstacles. The k-body security robots are arranged in squares (xi, yi) (0 ≤ xi ≤ n−1, 0 ≤ yi ≤ m−1), respectively, and can move to the upper, lower, left and right squares in a unit time. The security robot moves to the square with the jewel in the shortest path.

Find the maximum travel time it takes for one or more guard robots to reach the jeweled square when you are free to place jewels on the premises.

Constraints

* 1 ≤ n, m ≤ 5 × 104
* 1 ≤ k ≤ min (105, n x m)
* 0 ≤ xi ≤ n−1
* 0 ≤ yi ≤ m−1
* All given coordinates are different

Input


n m k
x1 y1
x2 y2
...
xk yk


All inputs are given as integers.
The first line is given n, m, k separated by blanks.
The coordinates (xi, yi) of the square where the guard robot is located are given in the second and subsequent lines k, separated by blanks.

Output

Output the travel time to the place where it takes the longest time for the security robot to reach in one line.

Examples

Input

20 10 1
0 0


Output

28


Input

20 10 2
0 0
17 5


Output

15


Input

20 10 3
0 0
17 5
6 9


Output

11

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define N (1<<18)
#define INF (1e9)
using namespace std;
struct po{
  int l,r,x;
  po(){};
  po(int l,int r,int x):l(l),r(r),x(x){}
};
const int base=1e5+2;
int segMin[2][2*N-1], segAdd[2][2*N-1];
int w,h,m,x[N],y[N];
vector <po> mp[2][N];
po LR[N];

//starry sky tree
void add(int a,int b,int x,int k,int l,int r,int idx){
  if(r<=a||b<=l) return;
  if(a<=l&&r<=b){segAdd[idx][k]+=x;return;} 
  add(a,b,x,2*k+1,l,(l+r)/2,idx);
  add(a,b,x,2*k+2,(l+r)/2,r,idx);
  int L=segMin[idx][2*k+1]+segAdd[idx][2*k+1];
  int R=segMin[idx][2*k+2]+segAdd[idx][2*k+2];
  segMin[idx][k]=min(L,R);
}

int getMin(int a,int b,int k,int l,int r,int idx){
  if (r<=a||b<=l) return INF;
  if (a<=l&&r<=b) return segMin[idx][k]+segAdd[idx][k];
  int L=getMin(a,b,2*k+1,l,(l+r)/2,idx);
  int R=getMin(a,b,2*k+2,(l+r)/2,r,idx);
  return min(L,R)+segAdd[idx][k];
}

void mk_LR(){
  for(int i=0;i<h&&w==1;i++)LR[base+i]=po(base,base,i%2);
  if(w==1)return;

  LR[base]=po(base,base,0),LR[base+1]=po(base,base+1,1);
  int mn=min(w,h),S,cnt=0;
  for(int i=1;i<mn;i++) cnt+=2*i;
  S=(w*h-cnt)/mn;
  if(w==2)S--;
  for(int i=base+2;;i++){
    int l=LR[i-2].l-1,r=LR[i-2].r+1,x=LR[i-2].x;

    if(S==0&&!x)l=LR[i-1].l,r=l+mn-2,S--;
    else if(S==0&&x)l=LR[i-1].l+1,r=LR[i-1].r,S--;
    else if(S<0) l+=2,r-=2;
    if(l>r)break;
    if(r-l+1>mn) l=LR[i-2].l,r=l+mn-1;
    if(S>0&&LR[i-2].r-LR[i-2].l+1==mn)l=LR[i-2].l+1,r=l+mn-1;
    if(r-l+1==mn)S--;
    LR[i]=po(l,r,x);
  }
}

void mk_mp(int d){
  for(int i=0;i<N;i++) mp[0][i].clear(),mp[1][i].clear();
  
  for(int i=0;i<m;i++){
    int idx=y[i]+(w-x[i]-1)+base;
    int c=LR[idx].l+min(y[i],x[i]);
    int a=idx%2,l=c-d/2,r=c+d/2;
    if(d%2==0){
      mp[a][idx-d].push_back(po(l,r,1));
      mp[a][idx+d+1].push_back(po(l,r,-1));

      mp[!a][idx-d+1].push_back(po(l+!a,r-a,1));
      mp[!a][idx+d].push_back(po(l+!a,r-a,-1));
    }
    else {
      mp[!a][idx-d].push_back(po(l-a,r+!a,1));
      mp[!a][idx+d+1].push_back(po(l-a,r+!a,-1));
      
      mp[a][idx-d+1].push_back(po(l,r,1));
      mp[a][idx+d].push_back(po(l,r,-1));
    }
  }
}


bool check(int d){
  mk_mp(d);
  memset(segMin,0,sizeof(segMin));
  memset(segAdd,0,sizeof(segAdd));
  for(int i=0;i<N;i++){

    for(int k=0;k<2;k++)
      for(int j=0;j<mp[k][i].size();j++)
	add(mp[k][i][j].l,mp[k][i][j].r+1,mp[k][i][j].x,0,0,N,k);
    
    if(LR[i].l&&!getMin(LR[i].l,LR[i].r+1,0,0,N,i%2))return 1;
  }
  return 0; 
}

int search(){
  int L=0,M,R=100001;
  while(L<R){
    M=(L+R)/2;
    if(!check(M)) R=M;
    else L=M+1;
  }
  return L;
}

int main(){
  cin>>w>>h>>m;
  for(int i=0;i<m;i++)cin>>x[i]>>y[i];
  if(w>h){
    swap(w,h);
    for(int i=0;i<m;i++)swap(x[i],y[i]); 
  }
  mk_LR();
 
  cout <<search()<<endl;
  return 0;
}