6. Ilúzia luxusu

Keď sa chcú normálni ľudia vyvyšovať nad svoje okolie a dať viditeľne najavo svoje bohatstvo alebo status, kúpia si športové auto, švajčiarske hodinky, alebo značkovú koženú kabelku. Ale čo majú robiť chudáci kockáči? Ako majú ukázať svojim známym že nie sú nijaký plebs, aby to pochopil aj ten najasociálnejší introvert?

Podnikaví KSPáci si založili firmu, ktorá je zameraná na presne tento trhový segment. Prišli na trh s novým produktom: luxusnými organickými šachovnicami. Každý kockáč, čo ju uvidí, zaručene zbledne závisťou!

Organické šachovnice sa vyrábajú z kôry šachovnicovníka balkánskeho, národného stromu Chorvátska. Táto kôra má veľmi charakteristické zafarbenie: v pravidelnej mriežke na nej prirodzene vznikajú krásne biele a čierne štvorčeky. Hotový zázrak prírody.

Priviezli sme z Chorvátska veľký obdĺžnik odrezanej kôry. Musíme ho nakrájať na šachovnice. Môžu byť rôzne veľké, ale čím väčšie tým lepšie. Keďže šachovnicovníky sú veľmi vzácne a treba ich kôru dovážať z takej diaľky, chceli by sme ju celú spotrebovať až do posledného štvorčeka.

Úloha

Máme nejaký obdĺžnik zložený z bielych a čiernych štvorčekov. Pri výrobe použijeme tento proces:

Nájdeme v obdĺžniku najväčšiu šachovnicu, ktorú z neho môžeme vyrezať. Šachovnica je definovaná ako ľubovoľne veľký štvorec, v ktorom sa nikde stranou nedotýkajú políčka rovnakej farby. Ak máme viaceré rovnako veľké možnosti, vyberieme najvrchnejšiu, a ak sú stále viaceré v rovnakej výške, najľavejšiu. Danú šachovnicu vyrežeme a môžeme predávať.

Toto opakujeme až kým nevyrežeme úplne každé políčko. Ku koncu, keď sa všetky väčšie minú, možno bude treba vyrezávať aj 1x1 šachovnice (jednotlivé štvorčeky). Naše marketingové oddelenie si s tým nejak poradí.

Zistite, koľko šachovníc ktorej veľkosti vznikne touto stratégiou.

Formát vstupu

V prvom riadku vstupu je výška obdĺžnika \(r\) a šírka obdĺžnika \(c\).

Zvyšok vstupu tvorí \(r\) riadkov, každý popisuje jeden riadok nášho čiernobieleho obdĺžnika.

Aby sme ušetrili trochu miesta, každý riadok je na vstupe zapísaný ako hexadecimálne číslo, zložené z presne \(c/4\) cifier (znakov 0-9A-F). Každá cifra teda udáva farbu štyroch štvorčekov. Čísla sú zapísané normálne, od veľkého konca (big-endian), čiže najvýznamnejšia cifra je vľavo. Napríklad hexadecimálny zápis CFF8 je v binárke 1100111111111000 – C je 1100 atď. Nulové bity sú čierne štvorčeky a jednotkové bity sú biele.

Šírka \(c\) je zaručene deliteľná štyrmi.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Najprv vypíšte riadok s číslom \(k\) – počtom rôznych veľkostí vyrobených šachovníc.

Potom vypíšte \(k\) riadkov a na každom dve kladné celé čísla: veľkosť (dĺžka strany) šachovnice, a počet kusov vyrobených šachovníc čo má túto veľkosť.

Veľkosti musia byť zoradené zostupne, čiže v takom poradí ako sme ich vyrezávali.

Príklady

Input:

15 20
55555
FFAAA
2AAD5
D552A
2AAD5
D542A
4AD4D
B52B2
52AAD
AD552
AA52D
AAAAA
5AA55
A55AA
5AA55

Output:

5
6 2
4 3
3 7
2 15
1 57

Na obrázku je znázornené poradie prvých 7 šachovníc, ktoré sme našli a vyrezali. Vidno, že prvá a druhá sú veľké 6x6, ďalšie tri sú 4x4, a potom režeme 3x3. Vyrezávanie pokračuje aj ďalej, ďalšími piatimi 3x3 a potom mnohými 2x2 a 1x1, ale tie už na obrázku nakreslené nie sú.

Input:

4 4
0
0
0
0

Output:

1
1 16

Aká smola, máme 16 čiernych štvorčekov… Marketingové oddelenie sa bude musieť fakt snažiť.

Input:

4 4
3
3
C
C

Output:

2
2 1
1 12

Input:

4 8
6A
95
9A
65

Output:

2
4 1
2 4