Осталось несколько дней до Корейского Нового года, и Джаехьюн пригласил свою семью в сад. Среди гостей есть дети. Чтобы сделать времяпровождение для них интереснее, Джаехьюн решил устроить игру в прятки.

Сад можно описать как таблицу $$$n \times m$$$ из единичных клеток. Некоторые (возможно ноль) из них заняты камнями, а остальные свободны. Две клетки называются соседними если у них есть общее ребро. Таким образом, у каждой клетки есть не более четырех соседей: два по горизонтали, и два по вертикали.

Так как сад можно описать как таблицу, клетки бывают двух видов: «черные» или «белые», как в шахматной доске. Первая клетка $$$(1, 1)$$$ черная. А затем, остальные клетки покрашены чередуясь. Клетки пронумерованы в 1-индексации.

Джаехьюн хочет превратить его сад в лабиринт расстановкой стен между двумя клетками. Стены могут быть размещены только между соседними клетками. Если поставить стену между двумя соседними клетками $$$a$$$ и $$$b$$$, тогда клетки $$$a$$$ и $$$b$$$ больше не считаются соседними. Можно идти прямо между двумя соседними клетками тогда и только тогда, когда нет прямой стены между ними.

Лабиринт должен обладать следующим свойством. Для каждой пары свободных клеток, должен быть ровно один простой путь между ними. Простой путь между клетками $$$a$$$ и $$$b$$$ это последовательность клеток, в которой первая клетка $$$a$$$, последняя $$$b$$$, все клетки различны, и любые две подряд идущие клетки являются соседями, между которыми не стоит стена.

Сначала, дети соберутся в клетке $$$(1, 1)$$$, и начнут играть в прятки. Ребенок может спрятаться в клетке если и только если это не стартовая клетка $$$(1, 1)$$$, и у нее есть ровно один свободный сосед. Джаехьюн посадил розы в черных клетках, так что там опасно прятаться. Поэтому Джаехьюн хочет построить лабиринт, в котором дети смогут прятаться только в клетках белого цвета.

Вам дана карта сада. Ваша задача — помочь Джаехьюну построить лабиринт.