СКБ Контур имеет множество филиалов, разбросанных по всему городу. Из-за их многочисленности клиенты часто путаются и не знают, куда им идти. Естественно, это недопустимо, поэтому руководство СКБ Контур решило создать справочник, который поможет клиентам выбрать именно то, что им нужно. Вам предстоит помочь нам в этом нелёгком деле.

Город представлен в виде сетки кварталов. Каждый квартал представляет собой квадрат, стороны которого являются улицами, а углы - перекрёстками. Будем считать, что все заведения, в том числе и филиалы СКБ Контур находятся именно на перекрёстках. Филиалы СКБ Контур бывают разного типа, например: сервисные центры, склады, магазины, учебные центры и т.д. Но, в принципе, в каждом из этих подразделений есть сотрудники по работе с клиентами, которые смогут дать всю необходимую информацию, поэтому нам будет достаточно для каждого перекрёстка в городе указать ближайшее подразделение СКБ Контур (или подразделения, если их несколько).

Такова наша задача, но мы не будем выполнять её всю. Как и полагается в индустрии программирования, мы сначала сделаем урезанный, отладочный вариант программы, который будет генерировать лишь часть информации, а именно: наша программа будет выдавать только типы ближайших подразделений.

Сервисные центры обозначим числом 1, склады — 2, магазины — 4, учебные центры — 8, и т.д. Всего различных типов подразделений будет не больше 11. Каждому перекрёстку назначим число, равное сумме обозначений типов подразделений, находящихся на данном перекрёстке (заметим, что на одном перекрёстке не может быть нескольких подразделений одного типа. Перекрёстки, на которых не находится ни одного подразделения СКБ Контур, обозначим числом 0.

Расстояние будем измерять количеством отрезков улиц, которые нам нужно пройти (см. рисунок). Например, расстояние от одного угла квартала до противоположного равно двум. От нас требуется найти для каждого перекрёстка, на котором не находится подразделений СКБ Контур, число равное сумме обозначений типов ближайших подразделений. Например, если на расстоянии 1 от данного перекрёстка нет подразделений СКБ Контур, на расстоянии 2 — подразделение типа 16, на расстоянии 2 (в другом направлении) — два подразделения типа 8 и одно подразделение 4, и больше нет подразделений на расстоянии 2, то данный перекрёсток надо обозначить числом 28 = 16 + 8 + 4. Подразделения, удалённые дальше, чем на 5 от данного перекрёстка, мы не рассматриваем. Таким образом, если для данного перекрёстка нет подразделений СКБ Контур находящихся ближе, чем в 6 кварталах, то мы обозначим его числом 0.

В первой строке содержатся целые числа H и W в пределах от 1 до 150 — количество улиц "по вертикали" и "по горизонтали" соответственно. Затем идёт H строк по W чисел в каждой, где i-е число в j-й строке описывает типы подразделений на перекрёстке i-й "вертикальной" улицы и j-й "горизонтальной".

Вы должны выдать H строк по W чисел в каждой, где i-е число в j-й строке будет равно сумме обозначений типов самых близких подразделений, если на перекрёстке i-й "вертикальной" улицы и j-й "горизонтальной" нет подразделений СКБ Контур, и −1 в противном случае.