시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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 n × n 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 (0, 0), a prawy górny róg - współrzędne (n, n). 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.

입력

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n oraz k (1 ≤ n ≤ 1 000, 1 ≤ k ≤ n2) oznaczające długość boku sadu oraz liczbę synów Bajtazara. Kolejne n wierszy zawiera opis zawartości poszczególnych kwadratów sadu. Każdy z tych wierszy zawiera n znaków x i/lub . oznaczających odpowiednio kwadrat zawierający i niezawierający jabłoni.

출력

Twój program powinien wypisać na wyjście k wierszy opisujących przykładowy podział sadu na działki. Każdy z wierszy powinien zawierać cztery liczby całkowite x1, y1, x2, y2 oznaczające współrzędne lewego dolnego (x1, y1) i prawego górnego (x2. y2) 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.

예제 입력 1

6 5
..x..x
..x...
....x.
xx.x.x
......
......

예제 출력 1

0 0 3 4
0 4 5 5
5 4 6 6
3 0 6 4
0 5 5 6

힌트