Програмчлалын олимпиадын бодлогын архив

КтМС-ын зогсоол дараах хэлбэртэй байдаг. 6*6 тэгш өнцөгт хэлбэртэй байрлана. Та машинаа гаргах гэтэл таны машиныг бусад машин бөглөн зогсожээ. Та маш яаралтай ажилтай тул гарах хэрэгтэй болсон. Машинуудын эзэн нь мөд гарч ирэхгүй бөгөөд тэдгээр машинуудын араа нь салгаастай байгаа. Та өөрийн болон бусад машиныг урагш хойш түрж болно гэхдээ эргүүлэх боломж байхгүй. Таны даалгавар бол хэдэн үйлдэл хийж байж машинаа гаргаж авах вэ гэдгийг тооцоолох юм. Зогсоолын гарц нь 3 дугаар мөрний 6 дугаар баганы ард байрлаж байгаа гэж үзнэ. Машинуудын урт 3 аас хэтрэхгүй.

Input

Эхний мөрөнд Машины тоо N (1<=N<=6) байрлана
Дараагийн N мөрөнд 4 тоо байрлах бөгөөд
Эхний тоо нь машины урт L (2<=L<=3)
Дараагийн тоо нь машины харж байгаа зүг буюу O (0<=O<=1)
O=1 байвал хэвтээ байгаа
O=0 байвал босоо байгна гэж үзнэ
Дараагийн хоёр тоо нь X,Y координатын тэнхлэг дээр байрлах координатууд
Нэгдүгээр машин бол таны машин гэж үзнэ.

Output

Хамгийн бага үйлдлээр машинаа гаргаж авах тоо
Хэрэв гаргаж авах боломжгүй бол -1 гэж гаргана

Example

Input:
8
2 1 2 3
2 1 1 1
2 0 1 5
2 1 5 5
3 0 6 1
3 0 1 2
3 0 4 2
3 1 3 6

Output:
18

Тайлбар:



4 ← ← ←, 2 → , 6 ↑, 3 ↑, 8 ← ←, 5 ↓ ↓ ↓, 7 ↓ ↓, 1 → → → → →. 
Ц. Дүүрэнбаярын нэрэмжит олимпиад - 2008 он.