Soricelul duce in continuare razboiul cu dusmanul traditional - pisica. Terenul de lupta este tot curtea, reprezentata pe harta soricelului de un dreptunghi de dimensiuni intregi, impartit pentru o mai usoara orientare in patrate de dimensiune 1. Pe harta sunt marcate pozitiile (patratele) unde se gasesc adaposturile soricelului, locuri in care pisica nu-l poate ataca, de asemenea sunt marcate obstacolele, locuri pe unde nu poate trece nici pisica, nici soarecele. Se cunoaste pozitia soricelului, undeva in curte in afara adaposturilor si pozitia pisicii. Pisica alearga de doua ori mai repede dacat soricelul, ceea ce inseamna ca in timp ce soricelul face un pas, pisica poate face unul sau doi pasi, un pas reprezentand deplasarea de la un patrat de pe harta la unul invecinat pe orizontala, verticala sau diagonala. Avand in minte harta curtii soricelul incearca sa afle spre ce adapost sa se indrepte astfel incat sa fie sigur ca pisica nu-l ajunge, indiferent de strategia ei de urmarire. 

Cerinta

Scrieti un program care sa determine toate adaposturile la care soricelul poate ajunge inaintea pisicii.

Date de intrare

Pe prima linie a fisierului de intrare soricel2.in sunt scrise doua numere reprezentand dimensiunile hartii. Pe urmatoarea linie este data pozitia soricelului. Pe linia a treia este pozitia pisicii. Pe linia a patra este numarul de adaposturi. Pe liniile urmatoare sunt pozitiile adaposturilor. Urmeaza o linie cu numarul de obstacole. Pe liniile urmatoare sunt pozitiile obstacolelor. Toate pozitiile sunt perechi de numere naturale reprezentand linia si coloana corespunzatoare. Numerotarea liniilor si coloanelor incepe de la 1. Numerele de pe aceeasi linie sunt separate de cate un spatiu.

Date de iesire

Prima linie a fisierului soricel2.out va contine numarul adaposturilor la care soricelul poate ajunge in siguranta. Pe liniile urmatoare sunt date coordonatele adaposturilor in acelasi format ca la fisierul de intrare. Adaposturile sunt scrise in ordinea crescatoare a liniei pe care se gasesc, iar adaposturile de pe aceeasi linie in ordinea crescatoare a coloanei. Daca nu exista nici un adapost in care sa intre soricelul inainte de a fi ajuns de pisica, in fisierul de iesire se va scrie doar numarul 0. 

Restrictii

Dimensiunile dreptunghiului nu depasesc 100 x 100. Exista cel mult 500 de adaposturi si 500 de obstacole. Pe pozitia initiala a soarecelui si a pisicii nu sunt adaposturi sau obstacole. De asemenea pozitia nici unui adapost nu coincide cu pozitia unui obstacol. Daca soricelul ajunge la patratul corespunzator unui adapost simultan cu pisica el este mancat inainte de a intra in adapost.

Exemplu

prof. Nistor Mot 
Colegiul National "N.Balcescu" - Braila