На перемене мы решили отдохнуть и поиграть в домино. Наша коробочка с доминошками была пуста, поэтому мы решили одолжить доминошки у учителя.
На нашу просьбу учитель отреагировал моментально. Он выложил на стол 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 градусов.
