7. Ochrana pred povodňami

Na obdĺžnikovom ostrove síce nebývajú povodne veľmi často, ale keď prídu, je to úplná katastrofa. Zaplavené sú lesy, lúky, námestia, domy a paneláky do výšky prvého poschodia. Takisto všade pláva množstvo odpadkov a opustených domácich zvieratiek. Obdĺžnikový ostrov sa totiž nachádza v strede obdĺžnikového jazera do ktorého vteká nie-až-tak-obdĺžniková rieka, ktorá pramení vo vzdialených trojuholníkových horách.

Pred rokom sa preto začalo s výstavbou protipovodňových ochranných múrov. Väčšina obyvateľov sa aktívne zapája a občas postaví štvorcový kúsok múru.¹ Ľudia si väčšinou stavajú múry vo svojom okolí, no niektorí podnikaví jedinci ich stavajú aj tam, kde ich netreba – napríklad v oblastiach, ktoré sú už celé obohnané múrom – alebo tam, kde sú absolútne zbytočné – napríklad osamotený metrový kus múru v strede poľa. A samozrejme, aj takéto aktivity im budú preplatené.

Ministerstvo má záznamy o každom kúsku múra, ktorý bol kedy postavený a Klub skeptických publicistov by ich rád preveril. Chcú o každom kúsku múru zistiť, aký prospešný bol pre spoločnosť a objaviť prípadné škandály v tejto kauze.

Úloha

Ostrov si môžeme predstaviť ako obdĺžnik rozdelený na \(w \times h\) štvorčekov. Každý štvorček môže byť buď prázdny, alebo na ňom môže byť postavená časť protipovodňovej ochrany.

Voda dokáže tiecť ôsmimi smermi a priteká na každé políčko na okrajoch ostrova. Samozrejme, voda nevie zaplaviť políčko, na ktorom je postavená protipovodňová ochrana.

Dostanete rozmery ostrova a pozície, kde sa postupne stavajú múry. Na začiatku je ostrov prázdny. Vašou úlohou je po postavení každého kúsku múra povedať, aká plocha je chránená pred vodou.

Formát vstupu

Na prvom riadku vstupu dostanete dve celé čísla \(w\) a \(h\) (\(1 \leq w,h \leq 2\,000\)), pričom \(w\) je šírka a \(h\) výška obdĺžnikového ostrova.

Na druhom riadku je číslo \(n\) (\(1 \leq n \leq w \times h\)) – počet štvorcových kúskov protipovodňového múru, ktoré budú postavené.

Každý z nasledujúcich \(n\) riadkov obsahuje dve čísla \(x_i\) a \(y_i\) (\(1 \leq x_i \leq w\), \(1 \leq y_i \leq h\)), ktoré označujú pozíciu, na ktorú bude postavený \(i\)-ty kúsok múra.

Formát výstupu

Vypíšte \(n\) takých riadkov, že v \(i\)-tom riadku bude jedno celé číslo – plocha územia, ktoré je chránená protipovodňovým múrom po postavení \(i\)-teho kúsku. To znamená počet takých políčok, na ktoré nevie pritiecť voda.

Príklad

Input:

4 4
10
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
2 2
3 4

Output:

1
2
3
4
5
6
7
9
9
10

Prvých 8 kúskov múra ochráni pred povodňami územie veľkosti \(3 \times 3\). Deviaty štvorček nemá vôbec žiadny účinok, lebo políčko \((2,2)\) už bolo chránené. Desiaty kúsok neuzavrie žiadne územie a teda prispeje len svojou plochou.