休息期间,我们决定放松一下,玩多米诺骨牌。我们的多米诺骨牌盒子是空的,所以我们决定借用老师的多米诺骨牌。
老师立即回应了我们的要求。他将 nm 块多米诺骨牌放在桌子上,形成一个 n × 2m 的矩形,使得每 n 行包含 m 块水平排列的多米诺骨牌。每张多米诺骨牌的每一半都包含数字(0 或 1)。
我们吃了一惊,老师微笑着说:“考虑一下n×2m矩阵中的多米诺骨牌排列。让我们计算矩阵的每一列该列中的数字之和,然后在所有这些和中找到最大的一个。你能重新排列矩阵中的多米诺骨牌,使最大和尽可能最小吗?注意,禁止改变多米诺骨牌的方向,它们都需要为了保持水平,尽管如此,多米诺骨牌可以旋转 180 度,作为奖励,我将把我所有的多米诺骨牌都给你。”
我们更吃惊了。当我们想知道发生了什么时,请帮助我们制作一个最佳的多米诺骨牌矩阵。
输入
第一行包含整数 n, m (1 ≤ n, m ≤ 103)。
接下来的几行是对教师矩阵的描述。接下来的 n 行中的每一行都包含 m 块多米诺骨牌。一张多米诺骨牌的描述是两个整数(0或1),没有空格——即多米诺骨牌左右半边的数字。
输出
以以下格式打印生成的多米诺骨牌矩阵:n 行,每行包含 m 个以空格分隔的多米诺骨牌。
如果有多个最优解,则打印其中任意一个。
示例
输入 #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
注意
考虑第一个样本的答案。其中,所有列的最大总和等于 1(列数是 6,而不是 3)。显然,这个最大值不能小于1,那么这样的矩阵就是最优的。
请注意,多米诺骨牌可以旋转 180 度。