| Codeforces Round 155 (Div. 2) |
|---|
| Закончено |
В подвале магазина, которым владеет Василий Петрович, расплодились крысы. Василий Петрович, возможно, и не замечал бы их присутствия, но они повадились пробираться на склад и красть оттуда продукты. Василий Петрович не может с этим больше мириться: он должен уничтожить крыс в подвале. Поскольку мышеловки уже изжили себя и совсем не помогают, а крысиным ядом потом можно отравиться и самому, он избрал радикальный способ: взорвать в подвале две гранаты (больше у него нет).
В данной задаче мы будем представлять подвал магазина в виде прямоугольной таблицы из n × m клеток. Некоторые клетки заняты стенами, а остальные — свободны. Василий Петрович понаблюдал за крысами и выяснил, что в определенный момент времени они ложатся спать, причем все время в одни и те же места. В этот удобный момент он и хочет взорвать гранаты. На плане своего подвала он отметил те клетки, в которых спят крысы. Эти клетки, разумеется, не заняты стенами.
Гранату можно взорвать только в клетке, не занятой стеной. Взрывная волна от гранаты распространяется следующим образом. Будем считать, что подрыв гранаты происходит в момент времени 0. В этот начальный момент времени взорвана только клетка, где подорвали гранату. Если в момент времени t взорвана некоторая клетка, то в момент времени t + 1 будут взорваны те соседние по стороне клетки, которые не заняты стенами (некоторые из них могли быть взорваны и до этого). Взрывная волна распространяется ровно d секунд, после чего мгновенно угасает.
Пример распространения взрывной волны: на первой картинке ситуация до взрыва, а на последующих картинках показаны взорванные клетки на моменты времени 0,1,2,3 и 4. Таким образом взрывная волна на картинке распространяется d = 4 секунды. Василий Петрович интересуется, можно ли выбрать две клетки для подрыва гранат таким образом, чтобы все клетки, в которых спят крысы, оказались взорваны. Напишите программу, которая это выясняет.
В первой строке записаны три целых числа n, m и d, разделенных одиночными пробелами (4 ≤ n, m ≤ 1000, 1 ≤ d ≤ 8). В следующих n строках записана таблица, задающая план подвала. Каждая строка таблицы состоит из m символов. Символ «X» означает, что соответствующая клетка занята стеной, символ «.» означает свободную клетку, символ «R» — свободную клетку, в которой спят крысы.
Гарантируется, что первая и последняя строки, а также первый и последний столбцы состоят из символов «X». На плане есть хотя бы две клетки, не занятые стенами. Имеется хотя бы одна клетка, в которой спят крысы.
Если невозможно взорвать все клетки, в которых спят крысы, выведите единственное целое число -1. Иначе выведите через пробел четыре целых числа r1, c1, r2, c2, означающих, что одну из гранат следует взорвать в клетке (r1, c1), а другую — в клетке (r2, c2).
Считайте, что строки таблицы пронумерованы сверху вниз от 1 до n, а столбцы слева направо от 1 до m. Поскольку r1 и r2 задают номера строк, а c1 и c2 — номера столбцов в таблице, то должны выполняться ограничения: 1 ≤ r1, r2 ≤ n, 1 ≤ c1, c2 ≤ m. В одной и той же клетке дважды взрывать гранату нельзя. Взрывные волны гранат могут пересекаться. Возможно, взрыв одной из гранат не уничтожит ни одной крысы, а взрыв другой уничтожит всех.
4 4 1
XXXX
XR.X
X.RX
XXXX
2 2 2 3
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
2 3 6 9
7 7 1
XXXXXXX
X.R.R.X
X.....X
X..X..X
X..R..X
X....RX
XXXXXXX
-1
