这是bzoj上AC的第700题，一定要是一道神题！！！
当初分组赛的时候讲过拖到现在才写……
我们考虑把垂直方向移动和水平方向移动分开来考虑，不合法的轮数取二者最小
假设考虑的是垂直方向移动，障碍其实就是类似与x线段一定在y线段之前移动的意思
不难想到拓扑图，如果我们求出了一个向上移动的拓扑图，
不难发现只向一个方向移动一定有解，那么合法的方案就是拓扑排序
而求不合法的操作呢？我们考虑把从前往后删除线段变成从后往前添加线段，
如果添加了一个向上移动的线段i，这个线段x坐标范围内出现一条拓扑排序在i前面的线段，那么不合法
如果添加向下移动的线段i，这是看x坐标范围内是否有拓扑排序在i后面的线段
这我们是可以通过x坐标离散化+线段树维护区间最大值最小值搞定的
那么问题就是我们怎么构造拓扑图
裸的想法是O(n2)的，肯定不行……
不难想到，如果i阻碍j，i阻碍k，j阻碍k，我们没必要连i-->k的边
但具体怎么做呢？对于平面内的线段，在某一个地方做一条垂直x轴的直线
与这条直线相交的线段（由于端点的相交允许，我们考虑左端点与直线相交，不考虑与右端点直线相交），构成的阻碍关系可以简化表示成a1-->a2-->a3-->……
这样我们可以顺着x轴做扫描线，然后按照右端点查询-删除-左端点加入-查询的顺序做
每次查询我们这个线段所连的边，只要是前驱覆盖和后继被覆盖即可，我们可以用平衡树来维护前驱后继
这样就只要构造4*n条边即可，那么问题也解决了
对于水平方向同样的道理，旋转一下坐标轴即可
写了10kb真是爽！！！
const inf=;
type point=record
x,y:longint;
end;
way=record
po,next:longint;
end;
line=record
x,op,id:longint;
end; var e:array[..] of way;
tree,tag:array[..*,..] of longint;
lin:array[..] of line;
a:array[..,..] of point;
son:array[..,..] of longint;
u,du,p,fa,b,loc,h,wh,w,q:array[..] of longint;
d:array[..] of longint;
sum,x,y,m,root,ans,i,t,n,len:longint; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure swap(var a,b:point);
var c:point;
begin
c:=a;
a:=b;
b:=c;
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function cmp(a,b:line):boolean;
begin
if a.x=b.x then exit(a.op<b.op) //注意因为是端点触碰允许，所以先做右端点的扫描线
else exit(a.x<b.x);
end; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
inc(du[y]);
end; procedure sortu(l,r:longint);
var i,j,x:longint;
begin
i:=l;
j:=r;
x:=d[(l+r) shr ];
repeat
while d[i]<x do inc(i);
while x<d[j] do dec(j);
if not(i>j) then
begin
swap(d[i],d[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sortu(l,j);
if i<r then sortu(i,r);
end; procedure sortl(l,r:longint);
var i,j:longint;
x,y:line;
begin
i:=l;
j:=r;
x:=lin[(l+r) shr ];
repeat
while cmp(lin[i],x) do inc(i);
while cmp(x,lin[j]) do dec(j);
if not(i>j) then
begin
y:=lin[i]; lin[i]:=lin[j]; lin[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if l<j then sortl(l,j);
if i<r then sortl(i,r);
end; procedure topsort;
var h,r,i,x,y:longint;
begin
h:=;
r:=;
for i:= to n do
if du[i]= then
begin
inc(r);
q[r]:=i;
end; while h<=r do
begin
x:=q[h];
i:=p[x];
while i<> do
begin
y:=e[i].po;
dec(du[y]);
if du[y]= then
begin
inc(r);
q[r]:=y;
end;
i:=e[i].next;
end;
inc(h);
end;
end; procedure cov(i,z:longint);
begin
tree[i,]:=min(tree[i,],z);
tree[i,]:=max(tree[i,],z);
tag[i,]:=min(tag[i,],z);
tag[i,]:=max(tag[i,],z);
end; procedure push(i:longint);
begin
if tag[i,]<inf then
begin
cov(i*,tag[i,]);
cov(i*+,tag[i,]);
tag[i,]:=inf;
end;
if tag[i,]> then
begin
cov(i*,tag[i,]);
cov(i*+,tag[i,]);
tag[i,]:=;
end;
end; procedure build(i,l,r:longint);
var m:longint;
begin
tree[i,]:=inf;
tag[i,]:=inf;
tree[i,]:=;
tag[i,]:=;
if l<>r then
begin
m:=(l+r) shr ;
build(i*,l,m);
build(i*+,m+,r);
end;
end; procedure ins(i,l,r,z:longint);
var m:longint;
begin
if (x<=l) and (y>=r) then cov(i,z)
else begin
m:=(l+r) shr ;
push(i);
if x<=m then ins(i*,l,m,z);
if y>m then ins(i*+,m+,r,z);
tree[i,]:=min(tree[i*,],tree[i*+,]);
tree[i,]:=max(tree[i*,],tree[i*+,]);
end;
end; function find(l,r,x:longint):longint;
var m:longint;
begin
while l<=r do
begin
m:=(l+r) shr ;
if d[m]=x then exit(m);
if d[m]>x then r:=m- else l:=m+;
end;
end; function ask(i,l,r,k:longint):longint;
var m,s:longint;
begin
if (x<=l) and (y>=r) then exit(tree[i,k])
else begin
m:=(l+r) shr ;
push(i);
if k= then
begin
s:=inf;
if x<=m then s:=min(s,ask(i*,l,m,k));
if y>m then s:=min(s,ask(i*+,m+,r,k));
end
else begin
s:=;
if x<=m then s:=max(s,ask(i*,l,m,k));
if y>m then s:=max(s,ask(i*+,m+,r,k));
end;
exit(s);
end;
end; function make(x,y,z:longint):line;
begin
make.x:=x;
make.id:=y;
make.op:=z;
end; procedure unique;
var i,t:longint;
begin
t:=;
for i:= to n do
begin
inc(t); d[t]:=a[i,].x;
inc(t); d[t]:=a[i,].x;
end;
sortu(,t);
m:=;
for i:= to t do
if d[i]<>d[m] then
begin
inc(m);
d[m]:=d[i];
end;
end; function cmp(i,j:longint):boolean; //判断阻碍关系
var mid,pa,pb:extended;
begin
mid:=(max(a[i,].x,a[j,].x)+min(a[i,].x,a[j,].x))/;
pa:=(mid-a[i,].x)/(a[i,].x-a[i,].x)*(a[i,].y-a[i,].y)+a[i,].y;
pb:=(mid-a[j,].x)/(a[j,].x-a[j,].x)*(a[j,].y-a[j,].y)+a[j,].y;
exit(pa<pb);
end; procedure rotate(x,w:longint);
var y:longint;
begin
y:=fa[x];
if fa[y]<> then
begin
if son[fa[y],]=y then son[fa[y],]:=x
else son[fa[y],]:=x;
end
else root:=x;
fa[x]:=fa[y];
son[y,-w]:=son[x,w];
if son[x,w]<> then fa[son[x,w]]:=y;
son[x,w]:=y;
fa[y]:=x;
end; procedure up(x:longint);
var y:longint;
begin
y:=fa[x];
while y> do
begin
if h[y]>h[x] then
begin
if son[y,]=x then rotate(x,)
else rotate(x,);
y:=fa[x];
end
else break;
end;
end; procedure sift(i:longint);
var j1,j2:longint;
begin
repeat
j1:=son[i,]; j2:=son[i,];
if (j1=) and (j2=) then exit;
if (j1=) or ((h[j1]>h[j2]) and (j2<>)) then rotate(j2,)
else if (j2=) or ((j1<>) and (h[j1]<h[j2])) then rotate(j1,);
until false;
end; procedure newnode(x:longint);
var p:longint;
begin
inc(t); inc(sum);
b[t]:=x; loc[x]:=t;
h[t]:=trunc(random*inf)+;
fa[t]:=; son[t,]:=; son[t,]:=;
if root= then
begin
root:=t;
exit;
end
else begin
p:=root;
repeat
if cmp(x,b[p]) then
begin
if son[p,]= then
begin
son[p,]:=t;
break;
end;
p:=son[p,];
end
else begin
if son[p,]= then
begin
son[p,]:=t;
break;
end;
p:=son[p,];
end;
until false;
fa[t]:=p;
up(t);
end;
end; procedure delete(x:longint);
begin
sift(x);
if fa[x]<> then
begin
if son[fa[x],]=x then son[fa[x],]:=
else son[fa[x],]:=;
end;
fa[x]:=;
dec(sum);
if sum= then root:=;
end; function pre(p,x:longint):longint;
var tm:longint;
begin
if p= then exit(-)
else begin
if cmp(b[p],x) then
begin
tm:=pre(son[p,],x);
if tm=- then exit(b[p])
else exit(tm);
end
else exit(pre(son[p,],x));
end;
end; function suffix(p,x:longint):longint;
var tm:longint;
begin
if p= then exit(-)
else begin
if cmp(x,b[p]) then
begin
tm:=suffix(son[p,],x);
if tm=- then exit(b[p])
else exit(tm);
end
else exit(suffix(son[p,],x));
end;
end; procedure work(p1,p2:longint);
var i,r,z,pr,su,no:longint;
begin
len:=;
fillchar(p,sizeof(p),);
fillchar(du,sizeof(du),);
r:=;
for i:= to n do
begin
inc(r); lin[r]:=make(a[i,].x,i,);
inc(r); lin[r]:=make(a[i,].x,i,);
end;
sortl(,r);
i:=; t:=; root:=;
while i<=r do
begin
z:=lin[i].x;
while (i<=r) and (lin[i].x=z) do
begin
if lin[i].op= then newnode(lin[i].id);
no:=lin[i].id;
pr:=pre(root,no);
su:=suffix(root,no);
if (pr<>-) and (pr<>no) then add(no,pr);
if (su<>-) and (su<>no) then add(su,no);
if lin[i].op= then delete(loc[no]);
inc(i);
end;
end;
topsort;
for i:= to n do
w[q[i]]:=i;
unique;
build(,,m);
for i:=n downto do
begin
x:=find(,m,a[wh[i],].x);
y:=find(,m,a[wh[i],].x);
dec(y);
if (u[i]=p1) or (u[i]=p2) then
begin
if (u[i]=) or (u[i]=) then no:= else no:=;
z:=ask(,,m,no);
if (no=) and (z>w[wh[i]]) or (no=) and (z<w[wh[i]]) then
ans:=min(ans,i);
end;
ins(,,m,w[wh[i]]);
end;
end; begin
randomize;
readln(n);
for i:= to n do
begin
read(a[i,].x,a[i,].y);
read(a[i,].x,a[i,].y);
if a[i,].x>a[i,].x then swap(a[i,],a[i,]);
end;
for i:= to n do
readln(wh[i],u[i]);
ans:=n;
work(,);
for i:= to n do
begin
swap(a[i,].x,a[i,].y);
swap(a[i,].x,a[i,].y);
if a[i,].x>a[i,].x then swap(a[i,],a[i,]);
end;
work(,);
writeln(ans);
for i:= to n do
writeln(q[i],'');
end.