В честь вашего дня рождения вы подготовили праздничный стол! Теперь вы хотите посадить за него как можно больше гостей.
Стол можно схематично представить в виде прямоугольника с высотой \(h\) и шириной \(w\), разбитого на \(h \times w\) ячеек. Будем обозначать через \((i, j)\) ячейку в \(i\)-й строке и \(j\)-м столбце прямоугольника (\(1 \le i \le h\); \(1 \le j \le w\)).
В каждую ячейку можно либо поставить тарелку для гостя, либо оставить её пустой.
Поскольку гостя нужно посадить рядом со своей тарелкой, можно ставить тарелки только на границу стола — в первую или последнюю строку прямоугольника, либо в первый или последний столбец. Формально, для любой ячейки \((i, j)\), в которую ставится тарелка, должно выполняться хотя бы одно из следующих условий: \(i = 1\), \(i = h\), \(j = 1\), \(j = w\).
Чтобы гостям было максимально комфортно, никакие две тарелки не должны находиться в ячейках, имеющих общую сторону или угол. Иными словами, если в ячейке \((i, j)\) находится тарелка, нельзя ставить тарелки в ячейки \((i - 1, j)\), \((i, j - 1)\), \((i + 1, j)\), \((i, j + 1)\), \((i - 1, j - 1)\), \((i - 1, j + 1)\), \((i + 1, j - 1)\), \((i + 1, j + 1)\).
Поставьте как можно больше тарелок на стол, не нарушая описанные выше условия.
Выходные данные
Для каждого набора входных данных выведите \(h\) строк по \(w\) символов каждый. Символ \(j\) в строке \(i\) должен быть равен \(1\), если в ячейку \((i, j)\) ставится тарелка, и \(0\) в противном случае. Если существует несколько решений, выведите любое из них.
Все тарелки должны стоять на границе стола. Никакие две тарелки не могут стоять в ячейках, соседних по стороне или углу. Число тарелок, выставленных на стол при этих условиях, должно быть максимальным возможным.
Разрешается выводить дополнительные пустые строки.
Примечание
В примере представлен единственный способ расставить \(6\) тарелок на стол в первом наборе входных данных.
Во втором наборе входных данных есть много способов расставить \(4\) тарелки, приведён один из них.
Поставить больше \(6\) тарелок в первом наборе входных данных или \(4\) тарелок во втором невозможно.