Problem: Problem

The penguins Fluoro is in an infinitely wide ice cube ($ sx $, $ sy $).
There is a hole in the trout ($ tx $, $ ty $) through which water can enter.
There are $ n $ lumps of ice on the ice, each in the square ($ x_i $, $ y_i $).


Fluoro can move up, down, left and right in four directions.
It's slippery on the ice, so when you move it keeps moving until it hits a block of ice.
When it hits a lump of ice, it stops just before the square with the lump of ice.
You can enter the hole by passing through the square of the hole.


Fluoro can stop in the middle by stepping on it only once.

It hurts when it hits a lump of ice, so I want to reduce the number of hits as much as possible.
Find the minimum number of hits before moving to a square with a hole ($ tx $, $ ty $).
If you can't reach it, print $-$ 1.

Constraints

The input satisfies the following conditions.

* $ 0 \ leq n \ leq 10 ^ 5 $
* $ 0 \ leq sx $, $ sy $, $ tx $, $ ty $, $ x_i $, $ y_i \ leq 10 ^ 9 $
* All given coordinates are different

Input

The input is given in the following format.


$ sx $ $ sy $
$ tx $ $ ty $
$ n $
$ x_1 $ $ y_1 $
...
$ x_n $ $ y_n $


All inputs are given as integers.
The coordinates of the cell where Fluoro is on the first line are given separated by blanks.
The coordinates of the cells with holes in the second line are given separated by blanks.
The third line gives the number of ice cubes $ n $.
The coordinates of the square with the ice block on the following $ n $ line are given, separated by blanks.

Output

Output the minimum number of hits before moving to a hole.
If you can't reach it, print $-$ 1.

Examples

Input

0 0
13 33
2
0 34
14 0


Output

0


Input

0 1
5 0
4
2 1
1 3
4 2
3 0


Output

4


Input

0 0
0 2
1
0 1


Output

-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using ll=int64_t;
//#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

ll read(){
	ll i;
	scanf("%" SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

struct Pos{
	int x,y;
	bool operator<(const Pos&rhs)const {
		return x!=rhs.x?x<rhs.x:y<rhs.y;
	}
};

map<Pos,int> cmp;
vector<Pos> crd;

const int Nmax=400010;
vi g[Nmax],rg[Nmax];
int d[Nmax],rd[Nmax];
void MakeGraph(Pos s,Pos t,vector<Pos> org,bool vert){
	if(!vert){
		swap(s.x,s.y);
		swap(t.x,t.y);
		for(auto&p:org)
			swap(p.x,p.y);
	}
	REP(k,2){
		map<int,vi> src,dst;
		src[s.x].PB(s.y);
		dst[t.x].PB(t.y);
		for(auto p:org){
			src[p.x+1].PB(p.y);
			src[p.x-1].PB(p.y);
			dst[p.x].PB(p.y-1);
		}
		for(auto&kv:src){
			int x=kv.first;
			sort(ALL(dst[x]));
			for(auto sy:kv.second){
				auto itr=lower_bound(ALL(dst[x]),sy);
				if(itr!=dst[x].end()){
					int ty=*itr;
					if(k){
						sy=-sy;
						ty=-ty;
					}
					Pos ss=vert?Pos{x,sy}:Pos{sy,x};
					Pos tt=vert?Pos{x,ty}:Pos{ty,x};
					if(cmp.count(ss)&&cmp.count(tt)){
						int si=cmp[ss];
						int ti=cmp[tt];
						g[si].PB(ti);
						rg[ti].PB(si);
					}
				}
			}
		}
		for(auto&p:org)
			p.y=-p.y;
		s.y=-s.y;
		t.y=-t.y;
	}
}
void SetDist(int n,vi*graph,int*dist,int src){
	REP(i,n)dist[i]=inf;
	queue<int> q;
	const auto set=[&](int v,int x){
		if(x<dist[v]){
			dist[v]=x;
			q.push(v);
		}
	};
	set(src,0);
	while(!q.empty()){
		int v=q.front();q.pop();
		for(auto to:graph[v])
			set(to,dist[v]+1);
	}
}
struct Line{
	int x,y1,y2,w;
};
ostream& operator<<(ostream&os,Line l){
	os<<"x:"<<l.x<<",y1:"<<l.y1<<",y2"<<l.y2<<",w"<<l.w;
	return os;
}
vector<Line> GetLines(vector<Pos> org,int*dist,bool vert){
	if(!vert){
		for(auto&p:org)
			swap(p.x,p.y);
		for(auto&p:crd)
			swap(p.x,p.y);
	}
	map<int,vi> pos,ice;
	for(auto p:org)
		ice[p.x].PB(p.y);
	for(auto&p:crd)
		pos[p.x].PB(p.y);
	vector<Line> res;
	for(auto kv:pos){
		int x=kv.first;
		vi&ys=ice[x];
		ys.PB(-inf);
		ys.PB(inf);
		sort(ALL(ys));
		vi&zs=kv.second;
		sort(ALL(zs));
		cerr<<x<<endl;
		cerr<<ys<<endl;
		cerr<<zs<<endl;
		int j=0;
		REP(i,int(ys.size())-1){
			assert(j<int(zs.size()));
			while(zs[j]<=ys[i])j++;
			assert(j<int(zs.size()));
			int mn=inf;
			while(j<int(zs.size())&&zs[j]<ys[i+1]){
				chmin(mn,dist[cmp[vert?Pos{x,zs[j]}:Pos{zs[j],x}]]);
				j++;
			}
			res.PB(Line{x,ys[i]+1,ys[i+1],mn});
		}
	}
	if(!vert){
		for(auto&p:crd)
			swap(p.x,p.y);
	}
	return res;
}
struct SegTree{
	vi buf;
	int s;
	SegTree(int n){
		s=1;
		while(s<n)s*=2;
		buf.resize(s*2,inf);
	}
	void Update(int i,int v){
		i+=s;
		buf[i]=v;
		while(i>>=1)
			buf[i]=min(buf[i*2],buf[i*2+1]);
	}
	int Get(int b,int e,int l,int r,int i){
		if(e<=l||r<=b)return inf;
		if(b<=l&&r<=e)return buf[i];
		return min(Get(b,e,l,(l+r)/2,i*2),Get(b,e,(l+r)/2,r,i*2+1));
	}
	int Get(int b,int e){
		return Get(b,e,0,s,1);
	}
};
struct Query{
	int y,x1,x2,v;
	bool operator<(const Query&rhs)const{
		if(y!=rhs.y)
			return y<rhs.y;
		else
			return x2<rhs.x2;
	}
};
int Sub(vector<Line> vs,vector<Line> hs){
	map<int,int> xs;
	for(auto l:vs){
		xs[l.x]=0;
	}
	for(auto l:hs){
		xs[l.y1]=0;
		xs[l.y2]=0;
	}
	{
		int tmp=0;
		for(auto&kv:xs){
			kv.second=tmp++;
		}
	}
	SegTree seg(xs.size());
	vector<Query> qs;
	for(auto l:vs){
		qs.PB(Query{l.y1,xs[l.x],-1,l.w});
		qs.PB(Query{l.y2,xs[l.x],-1,inf});
	}
	for(auto l:hs)
		qs.PB(Query{l.x,xs[l.y1],xs[l.y2],l.w});
	sort(ALL(qs));
	int ans=inf;
	for(auto q:qs){
		if(q.x2==-1){
			seg.Update(q.x1,q.v);
		}else{
			chmin(ans,seg.Get(q.x1,q.x2)+q.v);
		}
	}
	return ans;
}

signed main(){
	Pos s,t;
	vector<Pos> org;
	{
		{
			int x=read(),y=read();
			s=Pos{x,y};
		}
		{
			int x=read(),y=read();
			t=Pos{x,y};
		}
		cmp[s]=0;
		cmp[t]=0;
		int n=read();
		REP(i,n){
			int x=read(),y=read();
			cmp[Pos{x+1,y}]=0;
			cmp[Pos{x,y+1}]=0;
			cmp[Pos{x-1,y}]=0;
			cmp[Pos{x,y-1}]=0;
			org.PB(Pos{x,y});
		}
		for(auto p:org)
			cmp.erase(p);
		{ 
			int tmp=0;
			for(auto&p:cmp){
				crd.PB(p.first);
				p.second=tmp++;
			}
		}
		MakeGraph(s,t,org,true);
		MakeGraph(s,t,org,false);
	}
	int n=cmp.size();
	for(auto kv:cmp){
		cerr<<kv.first.x<<" "<<kv.first.y<<" "<<kv.second<<endl;
	}
	cerr<<n<<endl;
	REP(i,n){
		cerr<<"idx "<<i<<" "<<crd[i].x<<" "<<crd[i].y<<endl;
		cerr<<"to "<<g[i]<<endl;
	}
	SetDist(n,g,d,cmp[s]);
	SetDist(n,rg,rd,cmp[t]);
	if(d[cmp[t]]<=1){
		print(0);
		return 0;
	}
	vector<Line> sv=GetLines(org,d,true);
	vector<Line> sh=GetLines(org,d,false);
	vector<Line> tv=GetLines(org,rd,true);
	vector<Line> th=GetLines(org,rd,false);
	cerr<<sv<<endl;
	cerr<<sh<<endl;
	cerr<<tv<<endl;
	cerr<<th<<endl;
	int s1=Sub(sv,th);
	int s2=Sub(tv,sh);
	int ans=min(s1,s2);
	if(ans>=inf/2){
		print(-1);
	}else{
		print(ans);
	}
}