Constellation

TimeLimit:2000MS  MemoryLimit:256MB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description

A star map in Berland is a checked field n × m squares. In each square there is or there is not a star. The favourite constellation of all Berland's astronomers is the constellation of the Cross. This constellation can be formed by any 5 stars so, that for some integer x (radius of the constellation) the following is true:

  • the 2nd is on the same vertical line as the 1st, but x squares up
  • the 3rd is on the same vertical line as the 1st, but x squares down
  • the 4th is on the same horizontal line as the 1st, but x squares left
  • the 5th is on the same horizontal line as the 1st, but x squares right

Such constellations can be very numerous, that's why they are numbered with integers from 1 on the following principle: when two constellations are compared, the one with a smaller radius gets a smaller index; if their radii are equal — the one, whose central star if higher than the central star of the other one; if their central stars are at the same level — the one, whose central star is to the left of the central star of the other one.

Your task is to find the constellation with index k by the given Berland's star map.

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 300, 1 ≤ k ≤ 3·107) — height and width of the map and index of the required constellation respectively. The upper-left corner has coordinates (1, 1), and the lower-right — (n, m). Then there follow n lines, m characters each — description of the map. j-th character in i-th line is «*», if there is a star in the corresponding square, and «.» if this square is empty.

Output

If the number of the constellations is less than k, output -1. Otherwise output 5 lines, two integers each — coordinates of the required constellation. Output the stars in the following order: central, upper, lower, left, right.

SampleInput 1
5 6 1
....*.
...***
....*.
..*...
.***..
SampleOutput 1
2 5
1 5
3 5
2 4
2 6
SampleInput 2
5 6 2
....*.
...***
....*.
..*...
.***..
SampleOutput 2
-1
SampleInput 3
7 7 2
...*...
.......
...*...
*.***.*
...*...
.......
...*...
SampleOutput 3
4 4
1 4
7 4
4 1
4 7
Submit
题目统计信息详细
总AC数11
通过人数8
尝试人数8
总提交量16
AC率50.00%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签
出处

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: