시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB219524731.126%

문제

최근에 고고학자들이 그리스-로마 건축을 발견했다. 이 장소는 R*C칸으로 모델링 되어 있다. 고고학자들은 각 칸에 빌딩이 있었는지 없었는지를 표시해 두었다.

고고학자들은 이 장소에 서로 다른 시대에 지어진 두 건물이 있었다는 사실을 알게되었다. 또, 두 건물의 바닥 모양은 정사각형이었다.

두 건물이 서로 다른 시대에 지어졌기 때문에, 바닥이 겹칠 수도 있다. 이때, 가능한 위치와 크기를 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 발견한 장소의 크기인 R과 C가 주어진다. (1 ≤ R ≤ 100, 1 ≤ C ≤ 100)

다음 R개의 줄에는 C개의 문자가 주어진다. 각 문자는 '.' 또는 'x'이고, '.'인 경우에는 그 칸에 건물의 흔적이 없었다는 뜻이고, 'x'는 건물이 있었다는 뜻이다.

출력

두 건물의 바닥의 왼쪽 위 좌표와 크기를 출력한다. 항상 답이 존재하는 경우만 주어진다.

예제 입력 1

3 3
xx.
xxx
...

예제 출력 1

1 1 2
2 3 1

예제 입력 2

4 6
xx....
xx.xxx
...xxx
...xxx

예제 출력 2

1 1 2
2 4 3

예제 입력 3

5 5
.....
xxx..
xxxx.
xxxx.
.xxx.

예제 출력 3

2 1 3
3 2 3
W3sicHJvYmxlbV9pZCI6IjI5NjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI5YWNcdWMyYTQtXHViODVjXHViOWM4IFx1YWM3NFx1Y2Q5NSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjZDVjXHVhZGZjXHVjNWQwIFx1YWNlMFx1YWNlMFx1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWFkZjhcdWI5YWNcdWMyYTQtXHViODVjXHViOWM4IFx1YWM3NFx1Y2Q5NVx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWM3YTVcdWMxOGNcdWIyOTQgUipDXHVjZTc4XHVjNzNjXHViODVjIFx1YmFhOFx1YjM3OFx1YjljMSBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjZTBcdWFjZTBcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NDAgXHVhYzAxIFx1Y2U3OFx1YzVkMCBcdWJlNGNcdWI1MjlcdWM3NzQgXHVjNzg4XHVjNWM4XHViMjk0XHVjOWMwIFx1YzVjNlx1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWQ0NWNcdWMyZGNcdWQ1NzQgXHViNDUwXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZTBcdWFjZTBcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NDAgXHVjNzc0IFx1YzdhNVx1YzE4Y1x1YzVkMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzJkY1x1YjMwMFx1YzVkMCBcdWM5YzBcdWM1YjRcdWM5YzQgXHViNDUwIFx1YWM3NFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWM1YzhcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWM4Y1x1YjQxOFx1YzVjOFx1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVhYzc0XHViYjNjXHVjNzU4IFx1YmMxNFx1YjJlNSBcdWJhYThcdWM1OTFcdWM3NDAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVhYzc0XHViYjNjXHVjNzc0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMmRjXHViMzAwXHVjNWQwIFx1YzljMFx1YzViNFx1Yzg0Y1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YmMxNFx1YjJlNVx1Yzc3NCBcdWFjYjlcdWNlNjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzFjXHVhY2FjXHVkNTVjIFx1YzdhNVx1YzE4Y1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWM3NzggUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBSICZsZTsgMTAwLCAxICZsZTsgQyAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFJcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IENcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjI5NCAmIzM5Oy4mIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTt4JiMzOTtcdWM3NzRcdWFjZTAsICYjMzk7LiYjMzk7XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFkZjggXHVjZTc4XHVjNWQwIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWQ3NTRcdWM4MDFcdWM3NzQgXHVjNWM2XHVjNWM4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YWNlMCwgJiMzOTt4JiMzOTtcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzc0IFx1Yzc4OFx1YzVjOFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViNDUwIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWJjMTRcdWIyZTVcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWM4OGNcdWQ0NWNcdWM2NDAgXHVkMDZjXHVhZTMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTY3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTVJBVk9KRUQiLCJkZXNjcmlwdGlvbiI6IjxwPkFyY2hlb2xvZ2lzdHMgcmVjZW50bHkgZm91bmQgdGhlIHJlbWFpbnMgb2YgR3JlY28tUm9tYW4gYXJjaGl0ZWN0dXJlLiBUaGUgbG9jYXRpb24gY2FuIGJlIG1vZGVsZWQgYXMgYSBncmlkIG9mIFImbWlkZG90O0Mgc3F1YXJlIGNlbGxzLiBGb3IgZWFjaCBvZiB0aGUgY2VsbHMsIGFyY2hlb2xvZ2lzdHMgaGF2ZSBkZXRlcm1pbmVkIGlmIHNvbWUgYnVpbGRpbmcgd2FzIHRoZXJlIG9yIGlmIHRoZSBjZWxsIGhhcyBhbHdheXMgYmVlbiBlbXB0eS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgZXhhbWluaW5nIHRoZSBhcnRpZmFjdHMgaW4gZGV0YWlsLCB0aGV5IGNvbmNsdWRlZCB0aGF0IHRoZSBsb2NhdGlvbiBjb250YWlucyB0d28gYnVpbGRpbmdzIGZyb20gZGlmZmVyZW50IHBlcmlvZHMgaW4gdGltZSwgYW5kIHRoYXQgdGhlIGZsb29yIHBsYW5zIG9mIGJvdGggYnVpbGRpbmdzIGFyZSBvZiBzcXVhcmUgc2hhcGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJlY2F1c2UgdGhlIGJ1aWxkaW5ncyB3ZXJlIGZyb20gZGlmZmVyZW50IHBlcmlvZHMgaW4gdGltZSwgaXQgaXMgcG9zc2libGUgdGhhdCB0aGVpciBmbG9vciBwbGFucyBvdmVybGFwLiBEZXRlcm1pbmUgdGhlIHBvc3NpYmxlIGxvY2F0aW9uIGFuZCBzaXplIChsZW5ndGggb2YgdGhlIHNpZGUgb2YgdGhlIHNxdWFyZSBvY2N1cGllZCBieSB0aGUgZmxvb3IgcGxhbikgZm9yIGVhY2ggYnVpbGRpbmcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgUiAoMSAmbGU7IFIgJmxlOyAxMDApIGFuZCBDICgxICZsZTsgQyAmbGU7IDEwMCksIHRoZSBzaXplIG9mIHRoZSBsb2NhdGlvbi4gRWFjaCBvZiB0aGUgbmV4dCBSIGxpbmVzIGNvbnRhaW5zIGEgc3Ryb25nIG9mIEMgY2hhcmFjdGVycyAmIzM5Oy4mIzM5OyAoZG90KSBvciAmIzM5O3gmIzM5OyAobG93ZXJjYXNlIGxldHRlcikuIFRoZSBjaGFyYWN0ZXIgJiMzOTsuJiMzOTsgbWVhbnMgdGhhdCBub3RoaW5nIHdhcyBmb3VuZCBpbiB0aGF0IGNlbGwsIHdoaWxlICYjMzk7eCYjMzk7IGluZGljYXRlcyB0aGF0IHRoZXJlIHdhcyBhIGJ1aWxkaW5nIHRoZXJlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIG9mIHRoZSB0d28gYnVpbGRpbmdzLCBvdXRwdXQgb24gYSBzaW5nbGUgbGluZSB0aGUgcm93IGFuZCBjb2x1bW4gb2YgaXRzIHVwcGVyIGxlZnQgY29ybmVyLCBhbmQgdGhlIHNpemUgb2YgdGhlIGJ1aWxkaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgdGVzdCBkYXRhIHdpbGwgZ3VhcmFudGVlIHRoYXQgYSBzb2x1dGlvbiBhbHdheXMgZXhpc3RzLCBhbHRob3VnaCBpdCBtYXkgbm90IG5lY2Vzc2FyaWx5IGJlIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #1 3번