Fișierul intrare/ieșire	ozn.in, ozn.out	Sursă	Baraj Shumen juniori 2014 - etapa 2
Autor	Cristian Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.4 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

OZN (clasele 8-9)

Bucureștiul este asediat de OZN-uri! Harta Bucureștiului are formă dreptunghiulară și este formată din M x N clădiri cu latura de o unitate. Se cunoaște înălțimea fiecărei clădiri. OZN-urile au formă pătrată și sunt caracterizate prin următoarele valori:

• dimensiunea (lungimea laturii, exprimată în unități);
• coordonatele centrului;
• altitudinea la care survolează.

Pentru a genera o rază laser distrugătoare, flota de OZN-uri trebuie să se poziționeze unul sub altul astfel încât centrele lor să fie aliniate pe verticală. OZN-urile se pot mișca după următoarele reguli:

• își mențin altitudinea constantă;
• pot zbura paralel cu axele hărții Bucureștiului;
• nu se pot ciocni de clădiri, dar pot zbura pe deasupra lor;
• nu pot părăsi, cu nicio parte a lor, perimetrul Bucureștiului (Ilfovul le dăunează).

Pentru a-și pregăti apărarea, Primăria dorește, în primă fază, să afle deasupra câtor clădiri distincte s-ar putea alinia centrele OZN-urilor.

Date de intrare

Fișierul de intrare ozn.in conține pe prima linie trei numere M N K, despărțite prin spații. M și N sunt numărul de linii și de coloane al hărții Bucureștiului, iar K este numărul de OZN-uri. Pe următoarele M linii se află câte N numere indicând înălțimile clădirilor Bucureștiului. Pe următoarele K linii se află descrierea câte unui OZN, indicată prin patru numere naturale L C D A cu semnificațiile:

• L – linia pe care se află centrul OZN-ului;
• C – coloana pe care se află centrul OZN-ului;
• D – dimensiunea laturii;
• A – altitudinea.

Date de ieșire

În fișierul de ieșire ozn.out se va scrie un singur număr, reprezentând numărul de coordonate la care OZN-urile se pot alinia.

Restricții

• 1 ≤ M, N ≤ 200
• 1 ≤ K ≤ 100
• înălțimile clădirilor și altitudinile OZN-urilor sunt cuprinse între 1 și 50.000
• pentru fiecare OZN:
  • 1 ≤ L ≤ M
  • 1 ≤ C ≤ N
  • 1 ≤ D ≤ min(M, N), iar D este întotdeauna impar

Exemplu

Explicație

Primul OZN are mărimea 1×1 (cât amprenta unei clădiri) și zboară la altitudinea 10. El poate atinge zonele roșii din prima figură de mai jos.

Al doilea OZN are mărimea 3×3 și zboară la altitudinea 20. Centrul său poate atinge zonele albastre din a doua figură de mai jos.

OZN-urile își pot alinia centrele în două locuri: la coordonatele (2, 4) și (4, 4).