Üks saar on jagatud $N$ maatükiks. Iga maatükk on ristküliku kujuga. Vaja on ehitada tee punktist $A$ punkti $B$ nii, et tee kulgeks mööda maatükkide servasid (sest keegi maaomanikest ei soovi, et tee tema maatüki mitmeks väiksemaks tükiks jagaks).</p>

Kirjutada programm, mis leiab lühima nõuetekohase tee punktist $A$ punkti $B$.

입력 형식

Tekstifaili esimesel real on maatükkide arv $N$ ($1 \le N \le 1000$). Järgneval $N$ real on maatükke defineerivate ristkülikute alumise vasakpoolse ja ülemise parempoolse nurga koordinaadid $X_0$, $Y_0$, $X_1$, $Y_1$. Viimasel kahel real on punktide $A$ ja $B$ koordinaadid $X_A$, $Y_A$ ja $X_B$, $Y_B$. Kõik koordinaadid on mittenegatiivsed täisarvud, mille väärtus ei ületa $1\,000\,000$. On teada, et punktid $A$ ja $B$ on maatükkide servadel. Lisaks on teada, et kõik maatükid on ühel saarel, kuigi saarel võib olla ka järvi.

출력 형식

Tekstifaili esimesele reale väljastada leitud tee pikkus $L$. Järgnevatele ridadele väljastada leitud tee lõikude otspunktide koordinaadid $X$, $Y$. Kui leidub mitu sama teepikkusega lahendust, väljastada ainult üks neist.

예제 입력

3
4 1 7 4
3 4 6 5
1 3 4 4
4 5
3 3

예제 출력

5
4 5
3 5
3 4
4 4
4 3
3 3