Zadanie

Cesty sú deravé aj steny sú deravé

Počet bodov: 20

Vraví sa, že objekty v spätnom zrkadle sú bližšie, než sa zdá. Janka však neverí veciam, ktoré sa len tak hovoria, ak nie je k informácii uvedený zdroj. Nacúvala preto nedávno do susedovho plota a spravila v ňom niekoľko dier. Čaká ju teraz brigáda a plot musí opraviť.

Diery chcela pôvodne opraviť s použitím horizontálnych lát, no práve prišla do obchodu a povedali jej, že na sklade majú laty len vertikálne. Janka je taktiež chudobný študent a preto chce kúpiť lát čo najmenej. Netrúfa si však žiadnu latu rozdeľovať na menšie.

Možete Janke pomôcť a povedať jej, koľko vertikálnych lát jednotlivych dĺžok potrebuje, aby mohla plot opraviť?

Úloha

Vypíšte počty jednotlivých dlžok vertikálnych lát, ktoré treba na opravenie plotu. Počet lát treba minimalizovať.

Vstup a Výstup

Na prvom riadku sa nachádzajú dve čísla \(n\) a \(m\) – výška a dĺžka zrazeného plotu. Nasleduje \(n\) stringov dĺžky \(m\) pozostávajúcich zo znakov “0” a “1”. Znak “0” reprezentuje dieru a znak “1” hovorí, že na danom mieste je plot nepoškodený.

Na výstup vypíšte vo vzostupnom poradí dĺžku laty a počet lát danej dĺžky, ktoré potrebujeme, oddelené medzerou.

V prvej sade \(1 \leq n,m \leq 100\). V druhej \(1 \leq n,m \leq 1000\).

Príklady

Input:

5 5
10010
10000
00110
10000
01000

Output:

1 3
2 3
4 1
5 1

Na opravu Janka potreje následujúce vertikálne laty: 3 laty dĺžky 1, 3 laty dĺžky 2, 1 latu dĺžky 4, 1 latu dĺžky 5.