在最近的一次地震后，亚得里亚海中浮现出了一座新岛屿！岛上大部分地方荒无人烟，但人们发现了一个不寻常的装置。这个装置很快就被大家称为“神谕”（oracle）。尽管神谕没有附带任何说明书，但一支由考古学家和计算机专家组成的顶尖团队成功理解了它的运作方式。

神谕可以提供关于岛上宝藏位置的信息。该岛被划分为一个由 $N$ 行和 $N$ 列组成的网格，行和列的编号均为 $1$ 到 $N$。网格中的某些单元格藏有宝藏。神谕可以回答形如“给定网格中的一个矩形，该矩形内有多少个单元格藏有宝藏？”的问题。

虽然神谕可以回答任意大小矩形的问题，但人们发现，请求的信息越具体（即矩形越小），神谕在回答时消耗的能量就越多。更具体地说，如果一个矩形包含 $S$ 个单元格，那么神谕回答该问题将恰好消耗 $1 + N \times N - S$ 单位的能量。

请编写一个程序，在能够与神谕交互的情况下，找出岛上所有藏有宝藏的单元格的位置。我们不希望在交互过程中消耗过多的能量——消耗的能量越少越好。并不要求消耗的能量是理论最小值——有关如何对你的解决方案进行评分的详细信息，请参阅“子任务”部分。

交互

这是一个交互式任务。你的程序通过标准输出向神谕提问，并通过读取标准输入来接收回答。

• 在程序开始时，应读取一个整数 $N$（$2 \le N \le 100$），表示网格的大小。
• 要向神谕提问，你的程序应输出一行，包含四个由空格隔开的整数 $R_1, C_1, R_2$ 和 $C_2$，满足 $1 \le R_1 \le R_2 \le N$ 且 $1 \le C_1 \le C_2 \le N$。如果这些条件不满足或格式不正确，你的程序在该测试点上将获得 $0$ 分。
• 神谕将回应一行，包含一个整数——表示给定矩形中藏有宝藏的单元格数量。更具体地说，即满足 $R_1 \le R \le R_2$ 且 $C_1 \le C \le C_2$ 且位于第 $R$ 行第 $C$ 列的单元格藏有宝藏的单元格数量。
• 当你的程序完成提问后，应在单行中输出 END。之后，应输出 $N$ 行，每行对应网格中的一行，每行包含一个由 $N$ 个字符 0（零）或 1（一）组成的字符串。第 $R$ 行的第 $C$ 个字符如果为 1，则表示第 $R$ 行第 $C$ 列的单元格中藏有宝藏，否则为 0。行号从上到下为 $1$ 到 $N$，列号从左到右为 $1$ 到 $N$。一旦你的程序输出了解答，程序的执行将自动终止。
• 为了与评测程序正确交互，你的程序需要在每次提问以及输出解答后刷新标准输出（flush）。提供的代码示例展示了如何进行此操作。

你可以认为，在每个测试点中，神谕都会正确回答问题，且宝藏的位置在交互开始之前就已经确定。换句话说，评测程序不是自适应的（non-adaptive），回答不会取决于你程序之前提出的问题。

代码示例

三种编程语言的代码示例均可在竞赛系统的“Tasks”页面下载。这些示例的目的仅在于展示如何与神谕进行交互；它们并不是正确的解决方案，可能无法获得任何分数。

子任务

每个测试点分值为 $10$ 分。如果你的程序输出不正确，该测试点将获得 $0$ 分。否则，你获得的分数取决于神谕所消耗的能量总单位数 $K$。更具体地说：

• 如果 $K \le 7/16 N^4 + N^2$，你将获得 $10$ 分。
• 否则，如果 $K \le 7/16 N^4 + 2 N^3$，你将获得 $8$ 分。
• 否则，如果 $K \le 3/4 N^4$，你将获得 $4$ 分。
• 否则，如果 $K \le N^4$，你将获得 $1$ 分。
• 否则，你将获得 $0$ 分。

此外，在占总分至少 40% 的测试数据中，$N$ 将不超过 $20$。

即使你的程序直接猜中正确答案（例如，甚至没有提出任何问题），你的输出也会被认为是正确的。

样例

样例输入 1

2
0
1
2

样例输出 1

1 1 1 1
1 2 1 2
2 1 2 2
END
01
11

说明

在上述样例中，左侧为程序的输出（提问和最终答案），右侧为输入（网格大小和神谕的回答）。 具体交互过程如下： 1. 程序读取网格大小 $N = 2$。 2. 程序询问矩形 $(1, 1)$ 到 $(1, 1)$，神谕回答 $0$。 3. 程序询问矩形 $(1, 2)$ 到 $(1, 2)$，神谕回答 $1$。 4. 程序询问矩形 $(2, 1)$ 到 $(2, 2)$，神谕回答 $2$。 5. 程序输出 END，并输出网格的宝藏分布： 第一行：01 第二行：11

测试

测试程序有两种方式：本地测试或通过竞赛系统测试。在这两种情况下，你都必须首先创建一个描述测试用例的文件。测试文件的第一行应包含整数 $N$。接下来的 $N$ 行应以与程序输出相同的格式描述宝藏的位置。例如，前一节中样例的测试文件如下：

2
01
11

若要通过竞赛系统进行测试，首先需要使用“Submit”页面提交程序的源代码，然后使用“Test”页面。竞赛系统会告诉你程序是否产生了正确的输出，并提供关于查询次数和所用能量单位数的信息。

若要在本地进行测试，请使用可从竞赛系统下载的 treasure_test 可执行文件。该文件的运行命令类似于 ./treasure_test ./my_solution input_file。输出将包含关于你的程序是否正确解决了该测试用例的反馈，而 treasure.log 文件将包含有关程序发出的查询和接收到的响应的信息。