Cerința

“Avioane pe hârtie” este un joc ce se joacă în doi, fiecare jucător având la dispoziţie o foaie de hârtie (de matematică) şi ceva de scris.

Pe foaia ta de matematică, ai desenat un caroiaj cu N linii şi N coloane. La un moment al jocului, în acest caroiaj sunt deja plasate M avioane, numerotate de la 1 la M. Fiecare avion e format din exact 10 celule (o celulă cabina, apoi 5 celule aripa mare, o celulă culoar şi 3 celule aripa mică). Avioanele desenate nu se suprapun şi în funcţie de modul în care sunt amplasate pot fi de 4 tipuri:

• 1 – cabina orientată spre nord;
• 2 – cabina orientată spre est.
• 3 – cabina orientată spre sud;
• 4 – cabina orientată spre vest.

Pentru a putea identifica un avion pe foaie, toate celulele acoperite de avion sunt marcate cu numărul de ordine al avionului. Poziţiile neacoperite de avioane au valoarea 0.

Adversarul, fără a vedea foaia ta, lansează L lovituri. Fiecare lovitură afectează o singură celulă a caroiajului. Dacă loviturile afectează cel puţin una dintre celulele acoperite de un avion, se consideră că avionul a fost avariat. Un avion avariat este considerat avion doborât dacă a fost lovită cabina sa sau cel puțin 5 celule dintre cele 10 ale sale.

Dată fiind configuraţia caroiajului şi poziţiile loviturilor lansate de adversar, să se determine:

a. numărul total de avioane desenate în caroiaj;
b. numărul de avioane de fiecare tip;
c. numărul de avioane avariate, fără a fi doborâte;
d. numărul de avioane doborâte.

Date de intrare

Fişierul avioane.in conţine pe prima linie numerele naturale N L, reprezentând dimensiunea caroiajului, respectiv numărul de lovituri lansate de adversar. Pe următoarele N linii se vor găsi câte N numere naturale, reprezentând configuraţia caroiajului, conform specificaţiilor din enunţ. Pe următoarele L linii se află câte două numere naturale X Y, reprezentând linia, respectiv coloana unei celule lovite. Numerele scrise pe aceeaşi linie sunt separate prin spaţii.

Date de ieșire

Fişierul avioane.out va conţine pe prima linie numărul total de avioane de pe foaie; pe următoarele 4 linii se vor scrie 4 numere naturale, câte unul pe linie, reprezentând în ordine numărul avioanelor de tip 1, tip 2, tip 3 și respectiv tip 4. Pe următoarea linie se va scrie numărul de avioane avariate, care nu au fost doborâte, iar pe ultima linie va fi scris numărul de avioane doborâte.

Restricții și precizări

• 8 ≤ N ≤ 300
• N/2 ≤ L ≤ 2*N
• Liniile şi respectiv coloanele caroiajului sunt numerotate de la 1 la N.

Exemplu:

avioane.in

8 5
0 0 0 0 0 0 0 0 
0 0 0 0 1 1 1 0 
0 0 0 0 0 1 0 0 
0 0 0 1 1 1 1 1 
0 0 2 2 2 1 0 0 
0 0 0 2 0 0 0 0 
0 2 2 2 2 2 0 0 
0 0 0 2 0 0 0 0 
6 6
5 3
3 6
7 3
8 5

avioane.out

2
0
0
2
0
2
0

Explicație

În matricea de 8x8 avem 2 avioane, ambele de tip 3. Cabinele sunt în coordonatele (5,6) și (8,4). Deci pe prima linie în fișierul de ieșire va fi 2, iar pe următoarele 4 linii numărul avioanelor de fiecare tip: 0, 0, 2, 0, fiecare pe linie nouă.

În această reprezentare avem 5 lovituri. Cu cele 5 lovituri am reușit să lovim ambele avioane, fără a lovi cabina sau cel puțin 5 lovituri/avion. Astfel următoarele 2 valori din fișierul de ieșire sunt 2 și 0.

În această diagramă nu mai putem adăuga un avion de tip 1 astfel pe ultima linie vom avea valoarea 0.