Školsko natjecanje iz informatike 2020. / Druga podskupina (3. i 4. razred) - 2. zadatak.

Keramičar Mirko slaže pravokutne pločice dimenzija X × Y centimetara. Sve pločice su jednake i crnobijele, tj. možemo ih prikazati kao pravokutnik od X × Y znakova koji mogu biti ’.’ (bijelo polje) ili ’#’ (crno polje). Evo primjera jedne pločice:

Nakon što je Mirko ovim pločicama pravilno popločao pod kupaonice, fotografirao je svoj uradak.

Fotografija prikazuje samo dio poda i u cijelosti obuhvaća neke pločice, dok neke mogu biti djelomično obuhvaćene fotografijom.

Evo primjera fotografije poda nastalog od gore prikazanih pločica (jedna od njih je osjenčana):

Napišite program koji, ne znajući dimenzije pojedinih pločica, analizira Mirkovu fotografiju na način da pronalazi najmanje moguće dimenzije pločice (u smislu površine) od kojih bi mogla nastati takva fotografija.

Napomene. Pločice su složene bez rotiranja i zrcaljenja. Uočite da rješenje uvijek postoji jer je u najgorem slučaju cijela fotografija jedna pločica.

Moguće je dokazati da je rješenje jedinstveno, tj. ne može se dogoditi da postoje dva različita pravokutnika (u smislu dimenzija) koja imaju istu i najmanju moguću površinu.

Ulazni podaci

U prvom su retku prirodni brojevi R i S (1 ≤ R, S ≤ 50), dimenzije fotografije. Sljedećih R redaka sadrži po S znakova koji opisuju fotografiju kao u tekstu zadatka.

Izlazni podaci

U prvi redak ispišite tražene dimenzije pločice X i Y (broj redaka pa broj stupaca) odvojene razmakom.

Primjer zadataka

Ulaz

2 10
.#.#.#.#.#
.#.#.#.#.#

Izlaz

1 2

Ulaz

3 3
.#.
#.#
.#.

Izlaz

2 2

Ulaz

24 9
..#####..
..#...#..
......#..
..#####..
..#......
..#...#..
..#####..
..#...#..
......#..
..#####..
..#......
..#...#..
..#####..
..#...#..
......#..
..#####..
..#......
..#...#..
..#####..
..#...#..
......#..
..#####..
..#......
..#...#..

Izlaz

6 7