1. Puddles

Катя и лужи (puddles)

Однажды весной Катя задумалась о том, что она нестерпимо хочет поехать на море. Она потянулась к экрану монитора, чтобы увидеть рекламу отдыха и… Разлила воду на матрицу размером M×N. К сожалению, матрица прямо на глазах превратилась в сушу и водоемы. Правда, скопление воды на матрице не разделенное сушей, трудно назвать морем, но на лужу оно действительно похоже. За один час все клеточки, в которых есть вода и смежные с сушей, высыхают, т.е. превращаются в сушу. Таким образом количество луж изменяется. Сначала Катя очень расстроилась, но потом ей стало интересно через сколько часов у нее на матрице будет ровно K луж.

Поскольку Катя не очень сильный программист, то эту задачу она оставляет для вас.

Формат ввода-вывода:

Программа puddles сначала читает с клавиатуры (стандартного устройства ввода) три целых числа M, N, K (1⩽ M,N ⩽10³,1⩽ K ⩽10⁶). Каждая из следующих M строк будет содержать N символов, каждый из которых может быть или d и это означает, что на этом элементе находится суша, или w – вода. Гарантируется, что в матрице Кати, после того как она разлила воду, есть и суша, и вода.

Программа выводит на экран (стандартное устройство вывода) единственное значение – время, когда в матрице будет ровно K луж или «No Solution» (без кавычек), если ответа не существует.

Пример входных и выходных данных