1891 年，弗雷德里克·飞利浦（Frederik Philips）在埃因霍温创立了他的灯泡公司，并做出了一个伟大的发现：灯泡可以向水平或垂直方向发出无限长的光线。凭借这一新发现，他希望彻底改变现代住宅的室内设计。

他计划与儿子杰拉德（Gerard）一起进行一项精心的安装工程。他们在房间里的一个 $N \times N$ 网格中安装了 $N^2$ 个灯泡。他们希望在尽可能少开启灯泡的情况下照亮整个房间，以节省电力。每个灯泡要么是垂直的（意味着它照亮其所在列的所有方格），要么是水平的（意味着它照亮其所在行的所有方格）。

下图展示了一个垂直灯泡（左）和一个水平灯泡（右）的示例。

不幸的是，他们在安装灯泡时没有注意，不记得哪些灯泡是水平的，哪些是垂直的。因此，他们进行了一些实验来找出应该使用哪些灯泡来照亮整个房间。杰拉德留在装有灯泡的房间里，而弗雷德里克在另一个房间操作开关。

在每次实验中，弗雷德里克打开或关闭每个灯泡，杰拉德报告总共照亮了多少个方格；被两个或多个独立灯泡照亮的方格只计算一次。实验期间开启多少个灯泡并不重要，但他们时间紧迫，理想情况下希望进行的实验次数越少越好。

帮助他们找到一种既能照亮整个房间又能使用最少灯泡的灯泡布置方案。他们最多可以进行 $2\,000$ 次实验。然而，如果使用的实验次数更少，你将获得更高的分数。

交互

这是一个交互式问题。

• 你的程序应首先读取一个整数 $N$，即网格的高度和宽度。
• 然后，你的程序应与评测机进行交互。要进行一次实验，你应该首先打印一行包含问号“?”的内容。在接下来的 $N$ 行中，输出一个 $N \times N$ 的网格，指定哪些灯泡被点亮。具体来说，在这些行中的每一行，输出一个长度为 $N$ 的字符串，由 '0'（关闭）和 '1'（开启）组成。然后，你的程序应读取一个整数 $\ell$ ($0 \le \ell \le N^2$)，即通过开启指定的灯泡所照亮的网格方格总数。
• 当你想要回答时，打印一行包含感叹号“!”的内容，后跟 $N$ 行与上述格式相同的网格。为了使你的答案被接受，这些灯泡必须照亮整个网格，且开启的灯泡数量必须尽可能少。

在此之后，你的程序应退出。

评测机是非自适应的，这意味着灯泡的网格在交互开始前就已经确定。

在进行每次实验后，请确保刷新标准输出；否则，你的程序可能会被判为“Time Limit Exceeded”。在 Python 中，只要你使用 input() 读取行，这就会自动完成。在 C++ 中，cout << endl; 除了打印换行符外还会刷新缓冲区；如果使用 printf，请使用 fflush(stdout)。

数据范围

• $3 \le N \le 100$。
• 你最多可以进行 $2\,000$ 次实验（打印最终答案不计入实验次数）。如果超过此限制，你将获得“Wrong Answer”判决。

你的解决方案将在一组测试组上进行测试，每个测试组都有一定的分值。每个测试组包含一组测试用例。要获得测试组的分数，你需要解决该测试组中的所有测试用例。

在最后一个测试组中，你的得分取决于你进行的实验次数，计算公式如下：

$$ \text{score} = \begin{cases} (2000 - Q) \cdot 29/900 & \text{if } 200 \le Q \le 2000, \\ 58 + (200 - Q) \cdot 4/23 & \text{if } 85 \le Q \le 200, \\ 78 & \text{if } Q \le 85, \end{cases} $$

其中 $Q$ 是在任何测试用例中使用的最大实验次数。得分将向下取整到最接近的整数。

下图显示了得分作为 $Q$ 的函数，如果你的程序解决了所有测试组，它将获得相应的分数。为了在本题中获得 100 分的满分，你必须在每个测试用例中使用最多 85 次实验。

测试工具

为了方便测试你的解决方案，我们提供了一个简单的工具供你下载。请查看 Kattis 问题页面底部的“attachments”。该工具可选择使用。请注意，Kattis 上的官方评测程序与此测试工具不同。

要使用该工具，请创建一个输入文件，例如“sample1.in”，它应以数字 $N$ 开头，后跟 $N$ 行指定网格的行，其中 V 表示该灯泡照亮其所在列，H 表示它照亮其所在行。例如：

5
VVHVH
HVHHV
VHHVV
HHHVH
HHVVV

对于 Python 程序，假设为 solution.py（通常运行方式为 pypy3 solution.py）：

python3 testing_tool.py pypy3 solution.py < sample1.in

对于 C++ 程序，首先编译它（例如使用 g++ -g -O2 -std=gnu++20 -static solution.cpp -o solution.out），然后运行：

python3 testing_tool.py ./solution.out < sample1.in

样例

在样例交互中，程序首先读取网格大小 $N = 5$。下图显示了隐藏的网格（程序不知道）以及许多潜在答案中的一个，它使用了五个灯泡来照亮整个网格。标记的灯泡被开启，较暗的方格被照亮。

程序执行了两次实验，如下图所示。在第一次实验中，使用左上角的两个垂直灯泡总共照亮了 10 个方格。第二次实验总共照亮了 13 个方格。最后，程序写出其答案（如上图所示）并退出。