题目背景

翻译自 CEOI 2013 Day 1。

这是一道 IO 交互题。

一次地震过后，亚得里亚海出现了一座新岛。在岛上发现了一个特殊装置，名叫“神谕”。尽管没有说明手册，但考古学家和计算机专家的队伍成功地理解了它的行为。

神谕提供了一些有关该岛宝藏位置的信息。该岛被分为一个 $N$ 行 $N$ 列的网格，其中行和列都从 $1$ 到 $N$ 编号。网格中的一些单元格包含宝藏。神谕只会回答以下形式的问题：“给定网格中的一个矩形，在这个矩形中，有多少个单元格包含宝藏？”

尽管神谕可以回答所有大小的矩形问题，但发现请求的信息越具体（矩形越小），神谕在回答时消耗的能量越多。更精确地说，如果一个矩形包含 $S$ 个单元格，则神谕将使用 $1 + N \times N - S$ 个单位的能量来回答。

题目描述

编写一个程序，通过与神谕交互的方式，确定该岛上所有含有宝藏的单元格的位置。我们不希望在此过程中使用过多的能量，能量使用越少越好。但是也不要求使用的能量数量是最小的，具体得分规则见最后的“说明/提示”。

这是一个交互式任务。您的程序使用标准输出向神谕提问，并通过读取标准输入来获得答案。

• 在程序开始时，它应该读取一个整数 $N$（$2 \leq N \leq 100$），表示网格的大小。
• 要向神谕提问，您的程序应输出一行包含 $4$ 个整数 $R_1$、$C_1$、$R_2$ 和 $C_2$，它们之间由空格分隔，使得 $1 \leq R_1 \leq R_2 \leq N$ 和 $1 \leq C_1 \leq C_2 \leq N$ 成立。如果条件不成立或行格式不正确，则您的程序在该测试运行中将得零分。
• 神谕将响应一个包含单个整数的行 - 包含宝藏的矩形中提供的单元格数。更确切地说，是 $R_1 \leq R \leq R_2$ 且 $C_1 \leq C \leq C_2$ 且位于行 $R$、列 $C$ 的单元格包含宝藏的单元格数（$R$，$C$）。
• 当程序完成提问（已经确定所有宝藏的位置）后，它应在新的一行上输出 END。然后，再输出 $N$ 行，每行包含 $N$ 个 0 或 1 字符的字符串。第 $R$ 行中的第 $C$ 个字符是 1，如果该行中列 $C$ 的单元格中有宝藏，则为 0，如果没有，则为 1。行从顶部到底部编号为 $1$ 到 $N$，列从左到右编号。一旦您的程序输出解决方案，程序的执行将会自动终止。

为了与评分器正确交互，需要在每个问题和写出解决方案后刷新标准输出，这是交互题的惯例。

在每个测试运行中，可以假定神谕必然正确回答问题，并且在交互之前宝藏的位置是确定的。换句话说，答案不会取决于程序先前问的问题（不会根据你问的问题来改变答案），它在每个测试点都是固定的。

输入格式

该任务是一个交互式任务。要成功完成任务，需要编写一个程序以最大化降低向神谕提问的次数和使用的能量。在程序开始时，输入岛屿的大小 $N$。

输出格式

通过输出行号和列号的方式向神谕询问包含宝藏的单元格数量。每当程序获得答案后，就要输出 END，然后将宝藏位置汇总并输出。最终得分将由程序使用的能量数量确定。具体评分标准在题目的最后面，具体格式可见输入输出的一组样例。

2
0
1
2

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

提示

样例解释

每个测试用例得分为 $10$ 分。如果程序的输出不正确，则该测试用例得零分。否则，根据神谕使用的总能量单位 $K$ 来确定分数。

具体而言:

• 如果 $K ≤ \frac{7}{16} N^4 + N^2$，则得 $10$ 分。
• 否则，如果 $K ≤ \frac{7}{16} N^4 + 2N^3$，则得 $8$ 分。
• 否则，如果 $K ≤ \frac{3}{4} N^4$，则得 $4$ 分。
• 否则，如果 $K ≤ N^4$，则得 $1$ 分。
• 否则，得 $0$ 分。

此外，在至少占总分 $40\%$ 的测试数据中，$N$ 将最多为 $20$。

总而言之，花费的能量越少，你的得分就越高。

交互库/SPJ 提供者：