În urma bombardamentelor din 11 septembrie 2001, clădirea Pentagonului a suferit daune la unul din pereții clădirii. Imaginea codificată a peretelui avariat se reprezintă sub forma unei matrice cu m linii și n coloane, ca în figura de mai jos:

1110000111
1100001111
1000000011
1111101111
1110000111

unde 1 reprezintă zid intact, iar 0 zid avariat. Sumele alocate pentru refacerea Pentagonului vor fi donate celor care vor ajuta americanii să refacă această clădire prin plasarea, pe verticală, a unor blocuri de înălțimi k, k=1, …, m, și lățime 1, în locurile avariate.

Cerința

Pentru o structură dată a unui perete din clădirea Pentagonului, determinaţi numărul minim al blocurilor, de înălţimi k=1, k=2, …, k=m, necesare refacerii clădirii.

Date de intrare

Fișierul de intrare pentagon.in conține pe prima linie dimensiunile m şi n ale peretelui clădirii, iar pe următoarele m linii câte o secvență de caractere 1 sau 0 de lungime n.

Date de ieșire

Fișierul de ieșire pentagon.out va conține pe câte o linie, ordonate crescător după k, perechi de forma k nr, unde k este înălțimea blocului, iar nr este numărul de blocuri de înălțime k, separate prin câte un spaţiu.

Restricții și precizări

• 1 ≤ m, n ≤ 200
• nu se vor afișa blocurile de înălțime k, a căror număr este zero (0).

Exemplu:

pentagon.in

5 10
1110000111
1100001111
1000000011
1111101111
1110000111

pentagon.out

1 7
2 1
3 2
5 1