Павел обожает клетчатые лабиринты. Клетчатый лабиринт — это прямоугольный лабиринт размера n × m, где каждая клетка либо свободна, либо является стеной, а перемещаться из одной клетки в другую можно только в том случае, если они обе свободные и имеют общую сторону.

Павел нарисовал клетчатый лабиринт, все свободные клетки которого образуют связную область, то есть из любой свободной клетки можно добраться до любой другой. Павлу не нравится, что в его лабиринте слишком мало стен. Он хочет превратить ровно k свободных клеток в стены таким образом, чтобы все оставшиеся свободные клетки по прежнему образовывали бы связную область. Помогите ему.