CF394C.Dominoes

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 × 2_m_ 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 × 2_m_ 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.

课间休息时，我们决定放松一下，玩多米诺骨牌。我们的多米诺骨牌盒是空的，于是我们决定向老师借他的多米诺骨牌。

老师立刻回应了我们的请求。他将 $nm$ 张多米诺骨牌摆放在桌面上，构成一个 $n \times 2m$ 的矩形阵列，使得每一行恰好包含 $m$ 张水平放置的多米诺骨牌。每张多米诺骨牌的两个半块上各标有一个数字（0 或 1）。

我们大吃一惊，老师微笑着说道：“考虑一个在 $n \times 2m$ 矩阵中摆放多米诺骨牌的方案。对矩阵的每一列，计算该列中所有数字之和；然后在所有这些列和中找出最大值。你们能否重新排列这些多米诺骨牌（即调整它们在矩阵中的位置），使得该最大列和尽可能小？注意：不允许改变多米诺骨牌的朝向——所有骨牌必须保持水平放置；但允许将任意骨牌绕其中心旋转 $180^\circ$（即翻转其两端数字的顺序）。作为奖励，我将把全部多米诺骨牌送给大家。”

我们更加震惊了。就在我们百思不得其解之际，请帮我们构造一个最优的多米诺骨牌矩阵。

The first line contains integers n, m (1 ≤ n, m ≤ 103).

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.

第一行包含两个整数 $n$、$m$（$1 \leq n, m \leq 10^3$）。

接下来的若干行描述教师的矩阵。接下来的 $n$ 行中，每行包含 $m$ 个骨牌。每个骨牌的描述为两个整数（0 或 1），中间不加空格——分别表示该骨牌左半部分和右半部分的数字。

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.

按如下格式输出多米诺骨牌的最终矩阵：共 n 行，每行包含 m 个用空格分隔的多米诺骨牌。

若存在多个最优解，输出其中任意一个即可。

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.

考虑第一个样例的答案。其中，所有列中的最大和为 $1$（列数为 $6$，而非 $3$）。显然，该最大值不可能小于 $1$，因此这样的矩阵是最优的。

注意：多米诺骨牌可以绕其中心旋转 $180^\circ$。