#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <cmath> #define LL long long #define print(k) cout<<#k"="<<k<<endl; using namespace std; struct State { LL state,step; }; struct Block { LL l,c; bool t; }block[20]; LL n,red; inline LL getr(LL x,LL k) { return (x&(7LL<<k*3))>>k*3; } inline bool check(LL x,LL k1,LL k2) { if(getr(x,k1)>=getr(x,k2)) swap(k1,k2); if(block[k1].t==block[k2].t) { if(block[k1].c!=block[k2].c) return true; if(getr(x,k1)+block[k1].l>getr(x,k2)) return false; else return true; } if(getr(x,k1)<=block[k2].c && getr(x,k1)+block[k1].l>block[k2].c && getr(x,k2)<=block[k1].c && getr(x,k2)+block[k2].l>block[k1].c) return false; else return true; } inline bool check(LL x) { LL i,j; for(i=0;i<n;i++) { if(getr(x,i)+block[i].l>6) { return false; } for(j=0;j<i;j++) { if(!check(x,i,j)) { return false; } } } return true; } inline bool done(LL x) { if(getr(x,red)+block[red].l==6) return true; return false; } int main() { //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); while(cin>>n) { LL i,j,k; LL lx,ly,rx,ry; State head,tail; tail.state=0; for(i=0;i<n;i++) { cin>>k>>lx>>ly>>rx>>ry; if(lx==rx) { block[i].t=0; block[i].l=abs(ly-ry)+1; block[i].c=lx; tail.state+=min(ly,ry)<<3*k; } else if(ly==ry) { block[i].t=1; block[i].l=abs(lx-rx)+1; block[i].c=ly; tail.state+=min(lx,rx)<<3*k; } else exit(-1); } cin>>red; set<LL> st;st.clear(); st.insert(tail.state); queue<State> q; tail.step=0; q.push(tail); LL ans=-1; while(q.size() && ans<0) { head=q.front(); ///if(getr(head.state,red)==0) print(getr(head.state,red)); if(done(head.state)) { ans=head.step; break; } for(i=0;i<n && ans<0;i++) { LL m=getr(head.state,i); for(k=1;k+m+block[i].l<=6 && ans<0 && check(head.state+k*(1LL<<3*i));k++) if(st.count(head.state+k*(1LL<<3*i))==0) { //print(m) print(k) tail.state=head.state+k*(1LL<<3*i); tail.step=head.step+1; q.push(tail); st.insert(tail.state); if(done(tail.state)) { ans=tail.step; break; } } for(k=1;m-k>=0 && ans<0 && check(head.state-k*(1LL<<3*i));k++) if(st.count(head.state-k*(1LL<<3*i))==0) { tail.state=head.state-k*(1LL<<3*i); tail.step=head.step+1; q.push(tail); st.insert(tail.state); if(done(tail.state)) { ans=tail.step; break; } } } q.pop(); } cout<<max(ans,1LL)<<endl; } return 0; }