Un robot punctiform se poate deplasa, în plan, în linie dreaptă în orice direcție. Robotul se găsește într-o poziție inițială S și trebuie să ajungă într-o poziție finală F, evitând coliziunile cu obstacolele existente în teren. Obstacolele sunt suprafețe poligonale convexe, cu interioarele și frontierele disjuncte. Spunem că robotul a intrat în coliziune cu un obstacol dacă poziția sa devine interioară obstacolului. Prin urmare, dacă robotul se deplasează de-a lungul unui obstacol, nu intră în coliziune cu acesta.

Cerință

Scrieți un program care să determine cel mai scurt traseu pe care robotul îl poate urma de la poziția sa inițială S la poziția sa finală F, fără a intra în coliziune cu niciun obstacol.

Traseul va fi precizat prin succesiunea punctelor critice (punctul inițial, punctele în care robotul își schimbă direcția și punctul final). Lungimea traseului este egală cu suma lungimilor segmentelor care îl compun.

Date de intrare

Fișierul de intrare robot.in conține pe prima linie coordonatele poziției inițiale și finale a robotului xS yS xF yF. A doua linie conține n - numarul de obstacole. Apoi, urmează n grupuri de linii ce descriu obstacolele. Prima linie dintr-o grupă conține k - numărul de vârfuri ale obstacolului, urmată de k linii ce sunt formate din coordonatele vârfurilor obstacolelor x y.

Date de ieșire

Fișierul de ieșire robot.out conține traseul robotului codificat ca o succesiune de puncte între care robotul se mișca în linie dreaptă. Pe prima linie se va scrie numărul nr de puncte de pe traseu. Pe următoarele nr linii se vor afișa coordonatele punctelor de pe traseu, în ordine de la punctul inițial la cel final.

Restricții

• 1 ≤ n ≤ 20
• $k_1+k_2+...+k_n ≤ 100$
• $x_i, y_i$ sunt numere reale cu două zecimale, $|x_i|, |y_i| ≤ 100 \ 000$
• Punctele S și F nu se află în interiorul nic unui obstacol
• Coordonatele se vor afișa în fișierul de ieșire cu două zecimale semnificative.
• Daca există mai multe trasee de lungime minimă, se va afișa o singură soluție.

Exemplu

robot.in

10 5 -10 –10
1
3
0 0
0 10
10.5 0

robot.out

3
10 5
10.5 0
-10 -10

Explicație

Distanța minimă este $\sqrt{0.5^2+5^2}+\sqrt{20.5^2+10^2}=27.83..$