题目描述

在一个 $N\times N$ 的棋盘上，每个格子里都有一枚硬币，其中 $N$ 是偶数。每个格子恰好有一枚硬币。恰好一半硬币是银币，另一半是铜币。

如果所有铜币都位于棋盘的左上部分，所有银币都位于棋盘的右下部分，则称硬币摆放是正确的。更精确地说：如果某条格子边界是两种硬币的分界线，那么铜币应该位于银币的左侧或上方。

原题此处有图 1：左侧展示正确摆放，右侧展示错误摆放。黑色圆点表示铜币，白色圆点表示银币。后期可在此处补入原题图。

现在给定一个不正确的硬币摆放。你需要通过交换尽量少的硬币对，将它变成正确摆放。

输入格式

输入第一行包含四个整数 $T,N,K_1,K_2$：

• $T$：测试编号；
• $N$：棋盘大小；
• $K_1,K_2$：用于评分的参数，见“评分方式”。

接下来 $N$ 行，每行包含 $N$ 个整数，描述初始硬币摆放。可用的整数为：

• 0：铜币；
• 1：银币。

输出格式

输出一个 $N\times N$ 的棋盘，表示正确摆放后的硬币布局，格式与输入中的棋盘相同。

输出中应恰好有一半整数为 0，另一半整数为 1。

样例

输入

0 4 1 5
0 0 1 0
0 0 0 1
0 1 1 1
1 1 0 1

输出

0 0 1 1
0 0 1 1
0 0 1 1
0 0 1 1

样例解释

输出中的硬币摆放是正确的。

从输入变成该输出需要交换 $3$ 对硬币，因此根据评分规则可得：

分。

如果输出如下方案，则可获得满分 $10$ 分：

0 0 0 0
0 0 0 1
0 1 1 1
1 1 1 1

注意：这个测试是样例测试，不属于正式评分的 $10$ 个测试。

评分方式

正式评分共有 $10$ 个测试，编号从 $1$ 到 $10$。每个测试单独评分，每个测试价值 $10$ 分。

如果程序输出了错误解，或超过时间、空间限制，或由于运行时错误等原因没有产生解，则该测试得 $0$ 分。

如果程序输出了正确解，得分取决于从输入变成你输出的方案所需交换的硬币对数。记这个数为 $K$。

• 若 $K\le K_1$，该测试获得满分 $10$ 分；
• 若 $K>K_2$，该测试获得 $0$ 分；
• 若 $K$ 属于区间 $[K_1,K_2+1]$，得分按下式计算：

分数精确到一位小数。

原题此处有图 2：展示测试得分与交换次数 $K$ 的关系。后期可在此处补入原题图。

测试数据

对所有正式测试均满足：

原题在测试数据表中给出了每个测试的参数以及一张模糊化后的初始摆放图。图中较暗的像素表示对应位置更可能是铜币，较亮的像素表示对应位置更可能是银币。

原题此处有测试 $1$ 到测试 $10$ 的模糊化硬币分布图。后期可在此处补入原题图。