Максим большой любитель всевозможных игр. В этот раз он играет в игру под названием «Heroes of might and magic III».

Каждый сценарий в ней играется на определенной карте, которая представляет собой прямоугольник из $$$n \times m$$$ клеток. Каждая клетка имеет свой тип ландшафта, например «трава», «болото», «песок» и т.д. Визуально, некоторые клетки с одинаковым типом ландшафта образуют компоненты связности$$$^{\ast}$$$. Этих компонент может быть много, однако Максиму нравятся сценарии, где на карте есть не более двух типов ландшафтов и суммарное количество компонент связности в точности равно $$$k$$$.

Вы, как самый опытный картостроитель, пообещали придумать карту, которая понравится Максиму. Сможете ли вы сдержать это обещание?

Компонента связности$$$^{\ast}$$$ – это связная область таблицы, состоящая из одного и того же символа, а также для любой пары клеток $$$(x_{1}, y_{1})$$$, $$$(x_{2}, y_{2})$$$, принадлежащих этой области, существует путь из $$$(x_{1}, y_{1})$$$ в $$$(x_{2}, y_{2})$$$$$$^{\ast}$$$, состоящий только из клеток этой связной области.

Путь в таблице из $$$(x_{1}, y_{1})$$$ в $$$(x_{2}, y_{2})$$$$$$^{\ast}$$$ – это последовательность клеток, которая начинается в $$$(x_{1}, y_{1})$$$, заканчивается в $$$(x_{2}, y_{2})$$$ и любые две рядом стоящие клетки в этой последовательности являются соседними по стороне.