C. Доминошки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

На перемене мы решили отдохнуть и поиграть в домино. Наша коробочка с доминошками была пуста, поэтому мы решили одолжить доминошки у учителя.

На нашу просьбу учитель отреагировал моментально. Он выложил на стол nm доминошек в виде прямоугольника n × 2m так, что в каждой из n строк лежало m доминошек, расположенных горизонтально. На каждой половинке каждой доминошки было написано число (0 или 1).

Мы опешили, а учитель улыбнулся и произнес: «Рассмотрим некоторое расположение доминошек в матрице n × 2m. Давайте посчитаем для каждого столбца матрицы сумму чисел в этом столбце. Далее среди всех таких сумм найдем максимальную. Сможете ли вы так переставить доминошки в матрице, чтобы описанная максимальная сумма была минимальна? Учтите, запрещено менять ориентацию доминошек, все они должны остаться горизонтальными, тем не менее доминошки разрешено поворачивать на 180 градусов. В награду за сделанное я с легкостью отдам вам все мои доминошки.»

Мы еще больше опешили. А пока мы недоумеваем от происходящего, помогите нам составить оптимальную матрицу из доминошек.

Входные данные

В первой строке записаны целые числа n, m (1 ≤ n, m ≤ 103). Далее следует описание матрицы, которую составил учитель. В каждой из следующих n строк содержится m горизонтальных доминошек: каждая доминошка обозначается двумя символами (0 или 1), записанными без пробела — цифры на левой и правой половине соответствующей доминошки.

Выходные данные

Выведите полученную матрицу из доминошек в формате: n строк, в каждой из которых по m доминошек, записанных через пробел.

Если оптимальных ответов несколько, выведите любой.

Примеры
Входные данные
2 3
01 11 00
00 01 11
Выходные данные
11 11 10
00 00 01
Входные данные
4 1
11
10
01
00
Выходные данные
11
10
01
00
Примечание

Рассмотрим ответ на первый пример. В нем максимальная сумма по столбцам равна 1 (количество столбцов — 6, а не 3). Очевидно, что меньше 1 эта сумма быть не может, значит такое расположение доминошек является оптимальным.

Обратите внимание, что доминошки можно поворачивать на 180 градусов.