Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-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

D. Rats

time limit per test

1 secondmemory limit per test

256 megabytesinput

input.txtoutput

output.txtRats have bred to hundreds and hundreds in the basement of the store, owned by Vasily Petrovich. Vasily Petrovich may have not noticed their presence, but they got into the habit of sneaking into the warehouse and stealing food from there. Vasily Petrovich cannot put up with it anymore, he has to destroy the rats in the basement. Since mousetraps are outdated and do not help, and rat poison can poison inattentive people as well as rats, he chose a radical way: to blow up two grenades in the basement (he does not have more).

In this problem, we will present the shop basement as a rectangular table of *n* × *m* cells. Some of the cells are occupied by walls, and the rest of them are empty. Vasily has been watching the rats and he found out that at a certain time they go to sleep, and all the time they sleep in the same places. He wants to blow up a grenade when this convenient time comes. On the plan of his basement, he marked cells with sleeping rats in them. Naturally, these cells are not occupied by walls.

Grenades can only blow up in a cell that is not occupied by a wall. The blast wave from a grenade distributes as follows. We assume that the grenade blast occurs at time 0. During this initial time only the cell where the grenade blew up gets 'clear'. If at time *t* some cell is clear, then at time *t* + 1 those side-neighbouring cells which are not occupied by the walls get clear too (some of them could have been cleared before). The blast wave distributes for exactly *d* seconds, then it dies immediately.

Vasily Petrovich wonders, whether he can choose two cells to blast the grenades so as to clear all cells with sleeping rats. Write the program that finds it out.

Input

The first line contains three integers *n*, *m* and *d*, separated by single spaces (4 ≤ *n*, *m* ≤ 1000, 1 ≤ *d* ≤ 8). Next *n* lines contain the table that represents the basement plan. Each row of the table consists of *m* characters. Character "X" means that the corresponding cell is occupied by the wall, character "." represents a empty cell, character "R" represents a empty cell with sleeping rats.

It is guaranteed that the first and the last row, as well as the first and the last column consist of characters "X". The plan has at least two empty cells. There is at least one cell with sleeping rats.

Output

If it is impossible to blow up all cells with sleeping rats, print a single integer -1. Otherwise, print four space-separated integers *r*_{1}, *c*_{1}, *r*_{2}, *c*_{2}, that mean that one grenade should go off in cell (*r*_{1}, *c*_{1}), and the other one — in cell (*r*_{2}, *c*_{2}).

Consider the table rows numbered from top to bottom from 1 to *n* and the table columns — from left to right from 1 to *m*. As *r*_{1} and *r*_{2} represent the row numbers, and *c*_{1} and *c*_{2} represent the column numbers in the table, they should fit the limits: 1 ≤ *r*_{1}, *r*_{2} ≤ *n*, 1 ≤ *c*_{1}, *c*_{2} ≤ *m*. It is forbidden to blow a grenade twice in the same cell. The blast waves of the grenades can intersect. It is possible that one grenade blast destroys no rats, and the other one destroys all of them.

Examples

Input

4 4 1

XXXX

XR.X

X.RX

XXXX

Output

2 2 2 3

Input

9 14 5

XXXXXXXXXXXXXX

X....R...R...X

X..R.........X

X....RXR..R..X

X..R...X.....X

XR.R...X.....X

X....XXR.....X

X....R..R.R..X

XXXXXXXXXXXXXX

Output

2 3 6 9

Input

7 7 1

XXXXXXX

X.R.R.X

X.....X

X..X..X

X..R..X

X....RX

XXXXXXX

Output

-1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 17:23:37 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|