# URAL1105[Observers Coloring]

CODE:

/*
PROGRAM: \$PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-22
DESCRIPTION:
\$DESCRIPTION
*/

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

#define end first
#define begin second
#define segment first
#define id second
typedef pair<double,double> segment;
typedef
pair<segment,int> segment_with_id;

int
N;
segment_with_id one[10000+1];
double
t[2][10000+1];
int
rid[10000+1];
int
d2ic;
pair<int,int> d2i[20000+2];
int
tidc;
int
tid[2][10000+1];
double
i2d[20000+2];
double
f[10000+1];
int
pre[10000+1];
int
best_id;
int
st1[(20000+2)*4];
int
st2[(20000+2)*4];
int
int

bool
sort_rule(const pair<int,int>& a,const pair<int,int>& b)
{

return
t[a.first][a.second]<t[b.first][b.second];
}

void
insert1(int L,int R,int p,int v,int root=1)
{

if
(L<=p&&p<=R)
{

if
(f[st1[root]]<f[v])
st1[root]=v;
if
(L==R) return;
int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
insert1(LL,LR,p,v,Lroot);
insert1(RL,RR,p,v,Rroot);
}
}

int
query1(int L,int R,int p,int root=1)
{

if
(p<L) return 0;
else if
(R<=p) return st1[root];
else

{

int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
int
a=query1(LL,LR,p,Lroot),b=query1(RL,RR,p,Rroot);
return
f[a]>f[b]?a:b;
}
}

void
insert2(int L,int R,int p,int v,int root=1)
{

if
(L<=p&&p<=R)
{

if
(f[st2[root]]-i2d[tid[1][st2[root]]]*2.0<f[v]-i2d[tid[1][v]]*2.0)
st2[root]=v;
if
(L==R) return;
int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
insert2(LL,LR,p,v,Lroot);
insert2(RL,RR,p,v,Rroot);
}
}

int
query2(int L,int R,int p,int root=1)
{

if
(R<p) return 0;
else if
(p<=L) return st2[root];
else

{

int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
int
a=query2(LL,LR,p,Lroot),b=query2(RL,RR,p,Rroot);
return
f[a]-i2d[tid[1][a]]*2.0>f[b]-i2d[tid[1][b]]*2.0?a:b;
}
}

int
main()
{

cin>>t[0][0]>>t[1][0]
>>
N;
d2i[d2ic++]=make_pair(0,0),
d2i[d2ic++]=make_pair(1,0);
for
(int i=1;i<=N;i++)
{

cin>>one[i].segment.begin>>one[i].segment.end;
one[i].id=i;
}

sort(one+1,one+N+1);
for
(int i=1;i<=N;i++)
{

t[0][i]=one[i].segment.begin,
t[1][i]=one[i].segment.end;
rid[i]=one[i].id;
d2i[d2ic++]=make_pair(0,i),
d2i[d2ic++]=make_pair(1,i);
}

sort(d2i,d2i+d2ic,sort_rule);
for
(int i=0;i<d2ic;i++)
{

if
(i&&t[d2i[i].first][d2i[i].second]!=t[d2i[i-1].first][d2i[i-1].second]) tidc++;
tid[d2i[i].first][d2i[i].second]=tidc;
i2d[tidc]=t[d2i[i].first][d2i[i].second];
}

f[best_id=0]=0;
for
(int i=1;i<=N;i++)
{

int
npre;
double
nf;
npre=0;
nf=i2d[tid[1][i]]-i2d[tid[0][i]];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

npre=query1(0,tidc,tid[0][i]);
nf=i2d[tid[1][i]]-i2d[tid[0][i]]+f[npre];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

npre=query2(0,tidc,tid[0][i]);
nf=f[npre]-i2d[tid[1][npre]]*2.0+i2d[tid[0][i]]+i2d[tid[1][i]];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

if
(f[i]>f[best_id]) best_id=i;
insert1(0,tidc,tid[1][i],i);
insert2(0,tidc,tid[1][i],i);
}

if
(f[best_id]>=(i2d[tid[1][0]]-i2d[tid[0][0]])*2.0/3.0)
{

while
{

}