CF394C Dominoes

课间休息时，我们决定放松一下，玩多米诺骨牌。我们的多米诺骨牌盒子是空的，所以我们决定向老师借多米诺骨牌。 老师立刻回应了我们的请求。他把 $nm$ 张多米诺骨牌排成一个 $n×2m$ 的矩形，使得每一行有 $m$ 张横向放置的多米诺骨牌。每张多米诺骨牌的每一半上都有一个数字（$0$ 或 $1$）。 我们感到很惊讶，老师微笑着说：“考虑某种多米诺骨牌在 $n×2m$ 矩阵中的排列。对于每一列，统计该列数值的和，然后在所有这些和中找到最大值。你能否重新排列这些多米诺骨牌，使得最大的列和尽量小？注意：骨牌不能变成竖着，必须保持水平方向排列，但允许将骨牌旋转 $180$ 度。作为奖励，我会把所有多米诺骨牌都送给你们。” 我们更加吃惊了。当我们还在奇怪发生了什么时，请你帮我们找出最优的骨牌矩阵。

第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 10^{3}$）。 接下来 $n$ 行描述老师给的骨牌矩阵，每行有 $m$ 张骨牌。每张骨牌用两个整数（$0$ 或 $1$）描述，表示骨牌左半部分和右半部分的数字，两个数字之间没有空格。

输出重排列后的骨牌矩阵，共 $n$ 行，每行 $m$ 个用空格分开的骨牌。 如果有多种最优解，输出任意一种。

考虑第一个样例的答案，这时所有列中的最大和等于 $1$（共有 $6$ 列，而不是 $3$ 列）。显然，这个最大值不能小于 $1$，所以这个矩阵是最优的。 注意，多米诺骨牌允许旋转 $180$ 度。 由 ChatGPT 5 翻译