На перемене мы решили отдохнуть и поиграть в домино. Наша коробочка с доминошками была пуста, поэтому мы решили одолжить доминошки у учителя.
На нашу просьбу учитель отреагировал моментально. Он выложил на стол nm доминошек в виде прямоугольника n × 2m так, что в каждой из n строк лежало m доминошек, расположенных горизонтально. На каждой половинке каждой доминошки было написано число (0 или 1).
Мы опешили, а учитель улыбнулся и произнес: «Рассмотрим некоторое расположение доминошек в матрице n × 2m. Давайте посчитаем для каждого столбца матрицы сумму чисел в этом столбце. Далее среди всех таких сумм найдем максимальную. Сможете ли вы так переставить доминошки в матрице, чтобы описанная максимальная сумма была минимальна? Учтите, запрещено менять ориентацию доминошек, все они должны остаться горизонтальными, тем не менее доминошки разрешено поворачивать на 180 градусов. В награду за сделанное я с легкостью отдам вам все мои доминошки.»
Мы еще больше опешили. А пока мы недоумеваем от происходящего, помогите нам составить оптимальную матрицу из доминошек.
Выходные данные
Выведите полученную матрицу из доминошек в формате: n строк, в каждой из которых по m доминошек, записанных через пробел.
Если оптимальных ответов несколько, выведите любой.
Примечание
Рассмотрим ответ на первый пример. В нем максимальная сумма по столбцам равна 1 (количество столбцов — 6, а не 3). Очевидно, что меньше 1 эта сумма быть не может, значит такое расположение доминошек является оптимальным.
Обратите внимание, что доминошки можно поворачивать на 180 градусов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
01 11 00
00 01 11
|
11 11 10
00 00 01
|
|
2
|
4 1
11
10
01
00
|
11
10
01
00
|