Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Constellation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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·10^{7}) — 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.

Examples

Input

5 6 1

....*.

...***

....*.

..*...

.***..

Output

2 5

1 5

3 5

2 4

2 6

Input

5 6 2

....*.

...***

....*.

..*...

.***..

Output

-1

Input

7 7 2

...*...

.......

...*...

*.***.*

...*...

.......

...*...

Output

4 4

1 4

7 4

4 1

4 7

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2021 00:14:58 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|