1. Tuším sme už raz ochraňovali 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 a pol sa preto začalo s výstavbou protipovodňových ochranných múrov. Väčšina obyvateľov sa aktívne zapájala a občas postavli š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.

Takéto aktivity im už nebudú preplatené.

Vďaka novele zákona o preplácaní protipovodňových múrov budú odteraz preplácané len múry, ktoré skutočne niečo ochránia. Novela zákona síce platiť bude, ale ako zistiť, či sú múry zbytočné? Ministerstvo vám teda dalo zákazku: Chcú o každom kúsku múru zistiť, aký prospešný bol pre spoločnosť, teda aké veľké územie bude chránené po jeho postavení.

Ú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.

Táto úloha sa líši od Ochrany pred povodňami tým, že je online, teda skutočne potrebujete odpovedať hneď po postavení múra.

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 \(a_i\) a \(b_i\), ktoré sa zmestia do 32-bitovej premennej. Súradnice pozície \(x_i, y_i\) (\(1 \leq x_i \leq w\), \(1 \leq y_i \leq h\)), kde bude postavený \(i\)-ty kúsok múra vypočítate nasledovne: Nech \(v\) je posledný vypísaný výsledok. Na začiatku nastavme \(v=0\). Potom \(x_i = a_i ~\mathrm{xor}~ v, y_i = b_i ~\mathrm{xor}~ v\), teda pozíciu získate z \(a_i, b_i\) zoxorovaním s predošlým výsledkom, pričom používame bitový xor (bitwise xor), v C++ ^.

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
0 3
3 1
1 2
6 7
6 4
5 4
4 4
11 11
10 13

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.