Ai

AI

Fişierul de intrare $ai.in$ conţine:
* pe prima linie o valoare naturală $n$, reprezentând numărul segmentelor ce compun reţeaua;

* pe a doua linie cinci perechi de valori naturale separate prin câte un spaţiu $T$~1~ $T$~2~ $S$~1~ $S$~2~ $S$~3~ $S$~4~ $R$~1~ $R$~2~ $R$~3~ $R$~4~ cu următoarea semnificaţie: $T$~1~ $T$~2~ reprezintă coordonatele nodului unde se află ţinta, $S$~1~ $S$~2~ coordonatele nodului în care este amplasată prima sursă, $S$~3~ $S$~4~ coordonatele nodului în care este amplasată a doua sursă, $R$~1~ $R$~2~ coordonatele poziţiei iniţiale a primului robot, respectiv $R$~3~ $R$~4~ coordonatele poziţiei iniţiale a celui de-al doilea robot;

* pe a treia linie o valoare naturală $k$, reprezentând numărul obstacolelor din reţea;

* pe următoarele $k$ linii se găseşte câte o pereche de valori naturale separate printr-un spaţiu. Fiecare prereche reprezintă coordonatele unui nod în care este amplasat un obstacol.
h2. Date de ieşire

h2. Restricţii
* $n ≤ 1 000$

* $k ≤ 150 000$

* la începutul experimentului poziţiile ţintei, surselor laser, roboţilor şi obstacolelor sunt diferite

* roboţii nu pot ocupa şi nu pot trece prin nodul în care se află ţinta,

* roboţii pot ocupa un nod în acelaşi timp.

* un robot nu poate proteja ţinta faţă de o rază decât atunci când este plasat exact într-un nod, nu şi atunci când se află între două noduri.

* un obstacol poate să aparţină în acelaşi timp atât unui zid orizontal cât şi unui zid vertical.

* dacă fişierul de ieşire conţine o singură valoare, se consideră că aceasta reprezintă răspunsul la prima cerinţă

* în toate testele efectuate, există cel puţin o posibilitate ca ţinta să fie apărată de către una dintre raze de unul dintre roboţi iar faţă de cealaltă rază să fie apărată de celălalt robot.

* pentru rezolvarea primei cerinţe se acordă $20%$ din punctaj; pentru rezolvarea ambelor cerinţe se acordă 100% din punctaj.
h2. Exemplu

5515

5514