Хорошо известно, что когда коты забираются в полые сосуды, они проявляют свойства жидкости.
Математик Петров часто наблюдал это явление на примере своих котов и даже провел серию экспериментов, создавая различные виды сосудов и помещая в них котов. Оказалось, что коты всегда выбирают положение как можно ниже, а точнее — минимизируют уровень самой высокой точки своего тела. В случае наличия нескольких углублений в сосуде, коты выбирают самое низкое, но только из тех, в которые они могут поместиться.
Петрову пришла в голову блестящая мысль: на самом деле котов можно использовать как аналоговые компьютеры для решения некоторых задач квантовой оптимизации! Чтобы проверить свою гипотезу, математик Петров разработал следующую математическую модель:
Представим сосуд как таблицу $T$ размера $n \times m$. Некоторые ячейки являются стенами, остальные — пустыми. Размещение кота в сосуде является оптимальным, если выполняются следующие условия:
- Кот занимает несколько пустых ячеек. Все ячейки, занятые котом, образуют связную фигуру из $k$ ячеек. Фигура является связной, если каждую её ячейку можно достичь из любой другой, перемещаясь по соседним (по стороне) ячейкам (при этом все промежуточные ячейки также должны быть заняты котом).
- Уровень самой высокой ячейки $h$, занятой котом, должен быть как можно ниже. Строки таблицы пронумерованы от $1$ до $n$, и строка считается тем выше, чем меньше её номер.
К сожалению, математик Петров не силен в программировании. Он просит вас определить номер строки самой высокой ячейки $h$, занятой котом, для заданной таблицы $T$ и объема кота $k$.
Входные данные
Первая строка содержит целые числа $n$, $m$ и $k$ ($1 \le n, m \le 1000$, $1 \le k \le 10^6$).
Следующие $n$ строк содержат по $m$ символов — описание таблицы $T$. $j$-й символ $i$-й строки соответствует ячейке на пересечении $i$-й строки и $j$-го столбца $T$. «#» означает, что эта ячейка является стеной, а «.» означает, что эта ячейка пуста.
Выходные данные
Выведите номер строки, содержащей самую высокую занятую ячейку при любом оптимальном размещении кота. Если кота невозможно разместить в сосуде, выведите «-1» (без кавычек).
Примеры
Примеры 1
6 11 7 ........... .......#... .......#... #......#... ########... #######..##
4
Примеры 2
6 11 15 ........... .......#... .......#... #......#... ########... #######..##
2
Примеры 3
5 11 30 ..#......## ........... ......#.... ......#.... ......#....
2
Примечание
Оптимальное размещение кота для каждого примера может выглядеть следующим образом:
