Dominoes

题意翻译

有一个 $n \times 2m$ 大小的棋盘,每一个多米诺骨牌占 $1 \times 2$ 的格子,且一定是横向摆放 即每一个多米诺骨牌可能是$\text{'11''10''01''00'}$中的一种 问将棋盘上的骨牌重新摆放(可以将骨牌左右颠倒)后,使每一列上$\text{'1'}$的个数的最大值最小的其中一种方案

题目描述

During the break, we decided to relax and play dominoes. Our box with Domino was empty, so we decided to borrow the teacher's dominoes. The teacher responded instantly at our request. He put $ nm $ dominoes on the table as an $ n×2m $ rectangle so that each of the $ n $ rows contained $ m $ dominoes arranged horizontally. Each half of each domino contained number (0 or 1). We were taken aback, and the teacher smiled and said: "Consider some arrangement of dominoes in an $ n×2m $ matrix. Let's count for each column of the matrix the sum of numbers in this column. Then among all such sums find the maximum one. Can you rearrange the dominoes in the matrix in such a way that the maximum sum will be minimum possible? Note that it is prohibited to change the orientation of the dominoes, they all need to stay horizontal, nevertheless dominoes are allowed to rotate by 180 degrees. As a reward I will give you all my dominoes". We got even more taken aback. And while we are wondering what was going on, help us make an optimal matrix of dominoes.

输入输出格式

输入格式

The first line contains integers $ n $ , $ m $ ( $ 1<=n,m<=10^{3} $ ). In the next lines there is a description of the teachers' matrix. Each of next $ n $ lines contains $ m $ dominoes. The description of one domino is two integers (0 or 1), written without a space — the digits on the left and right half of the domino.

输出格式

Print the resulting matrix of dominoes in the format: $ n $ lines, each of them contains $ m $ space-separated dominoes. If there are multiple optimal solutions, print any of them.

输入输出样例

输入样例 #1

2 3
01 11 00
00 01 11

输出样例 #1

11 11 10
00 00 01

输入样例 #2

4 1
11
10
01
00

输出样例 #2

11
10
01
00

说明

Consider the answer for the first sample. There, the maximum sum among all columns equals $ 1 $ (the number of columns is $ 6 $ , and not $ 3 $ ). Obviously, this maximum can't be less than $ 1 $ , then such matrix is optimal. Note that the dominoes can be rotated by $ 180 $ degrees.