Sad
Limit pamięci: 128 MB
Sędziwy Bajtazar jest właścicielem sadu, w którym rosną jabłonie wydające szczerozłote owoce.
Niestety, praca w sadzie jest ciężka, a Bajtazar nie ma już tyle sił co dawniej, postanowił więc
podzielić swój sad na działki, które da do uprawy swoim synom.
Bajtazar chciałby zapewnić każdemu z synów dostatnie życie, więc pragnie,
aby każdemu z nich przypadła w udziale co najmniej jedna drogocenna jabłoń.
Sad Bajtazara ma kształt prostokąta o wymiarach metrów.
Dla uproszczenia wprowadzamy w nim prostokątny układ współrzędnych, w którym lewy dolny róg
sadu ma współrzędne , a prawy górny róg - współrzędne .
Wiemy, w których kwadratach jednostkowych sadu rosną jabłonie.
Działki powstałe w wyniku podziału sadu powinny być prostokątami o bokach zawartych
w liniach siatki układu współrzędnych.
Działki nie mogą na siebie nachodzić - mogą jedynie stykać się bokami lub wierzchołkami -
i muszą pokrywać cały sad.
Wymiary działek nie mają znaczenia; istotne jest tylko to, aby każda działka zawierała
przynajmniej jedną jabłoń.
Możesz założyć, że żądany podział sadu jest możliwy.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz
(, ) oznaczające
długość boku sadu oraz liczbę synów Bajtazara.
Kolejne wierszy zawiera opis zawartości poszczególnych kwadratów sadu.
Każdy z tych wierszy zawiera znaków x i/lub .
oznaczających odpowiednio kwadrat zawierający i niezawierający jabłoni.
Wyjście
Twój program powinien wypisać na wyjście wierszy opisujących przykładowy
podział sadu na działki.
Każdy z wierszy powinien zawierać cztery liczby całkowite , , ,
oznaczające współrzędne lewego dolnego i prawego górnego
wierzchołka działki.
Kolejność, w jakiej działki zostaną podane na wyjściu, nie ma znaczenia -
już Bajtazar będzie wiedział, którą działkę przydzielić któremu synowi.
Przykład
Dla danych wejściowych:
6 5
..x..x
..x...
....x.
xx.x.x
......
......
poprawną odpowiedzią jest:
0 0 3 4
0 4 5 5
5 4 6 6
3 0 6 4
0 5 5 6
Autor zadania: Jakub Radoszewski.