← 返回题目列表

Codeforces · 32/D

D. 星座

中文机器翻译题面 查看原题

Berland 的星图是一个 n × m 方格的格子区域。每个方格中有或没有星星。伯兰德所有天文学家最喜欢的星座是十字星座。这个星座可以由任意 5 颗星组成,因此对于某个整数 x(星座的半径),以下情况成立:

- 第二个与第一个在同一垂直线上,但 x 平方
- 第三个与第一个在同一垂直线上,但 x 向下平方
- 第 4 个与第 1 个在同一水平线上,但左侧有 x 个方格
- 第 5 个与第 1 个在同一水平线上,但 x 向右平方

这样的星座数量可能非常多,所以它们都用从1开始的整数编号,原则如下:两个星座比较时,半径较小的星座索引较小;半径较小的星座索引较小;半径较小的星座索引较小。如果它们的半径相等——其中一个的中心恒星高于另一个的中心恒星;如果它们的中心恒星处于同一水平面,则其中一个的中心恒星位于另一颗中心恒星的左侧。

你的任务是根据给定的 Berland 星图找到索引为 k 的星座。

输入

第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 300, 1 ≤ k ≤ 3·107) — 分别是地图的高度和宽度以及所需星座的索引。左上角的坐标为 (1, 1),右下角的坐标为 (n, m)。接下来是 n 行,每行 m 个字符——地图的描述。第 i 行中的第 j 个字符是“*”,如果相应的方块中有一颗星,则“.”如果这个方块是空的。

输出

如果星座数量小于k,则输出-1。否则输出 5 行,每行两个整数 — 所需星座的坐标。按以下顺序输出星星:中央、上、下、左、右。

示例

输入 #1

5 6 1
....*.
...***
....*.
..*...
.***..

输出 #1

2 5
1 5
3 5
2 4
2 6

输入 #2

5 6 2
....*.
...***
....*.
..*...
.***..

输出 #2

-1

输入 #3

7 7 2
...*...
.......
...*...
*.***.*
...*...
.......
...*...

输出 #3

4 4
1 4
7 4
4 1
4 7