JOI 王国是一个被海洋包围的岛屿。JOI 王国的土地是一个由 $N$ 行 $N$ 列方格组成的网格。垂直方向为南北方向，水平方向为东西方向。从北向南第 $(r + 1)$ 行（$0 \le r \le N - 1$）且从西向东第 $(c + 1)$ 列（$0 \le c \le N - 1$）的单元格记为 $(r, c)$。

JOI 王国的女王 Anna 将邀请 Bruno 参加聚会。她现在正在选择聚会地点。她已经选定了 $K (= 7)$ 个聚会候选地点。候选地点编号为 $0$ 到 $K - 1$。候选地点 $i$ 为单元格 $(R_i, C_i)$。没有候选地点与海洋相邻。

聚会地点将在聚会当天确定。

在聚会前一天，为了帮助 Bruno 在不迷路的情况下到达聚会地点，Anna 将在每个单元格放置一面旗帜。在每面旗帜上，Anna 将写下一个 $1$ 到 $1\,000\,000\,000$ 之间的整数（包含边界）。

在聚会当天，只有候选地点的索引 $t$ ($0 \le t \le K - 1$) 会告诉 Bruno。之后，Bruno 将乘坐直升机到达一个不与海洋相邻的单元格。然后，Bruno 将开始向聚会地点移动。

Bruno 不知道他在哪里，但他知道北、南、东、西的方向。Bruno 只能看到他当前单元格及其周围 8 个单元格的旗帜。换句话说，当 Bruno 在单元格 $(a, b)$ ($1 \le a \le N - 2, 1 \le b \le N - 2$) 时，他只能看到以下 9 个单元格的旗帜： $(a - 1, b - 1), (a - 1, b), (a - 1, b + 1), (a, b - 1), (a, b), (a, b + 1), (a + 1, b - 1), (a + 1, b), (a + 1, b + 1)$

Bruno 可以采取以下 5 种行动之一： 行动 0：Bruno 向东移动一格。即，他从单元格 $(a, b)$ 移动到 $(a, b + 1)$。 行动 1：Bruno 向西移动一格。即，他从单元格 $(a, b)$ 移动到 $(a, b - 1)$。 行动 2：Bruno 向南移动一格。即，他从单元格 $(a, b)$ 移动到 $(a + 1, b)$。 行动 3：Bruno 向北移动一格。即，他从单元格 $(a, b)$ 移动到 $(a - 1, b)$。 * 行动 4：Bruno 认为聚会将在他当前所在的单元格举行，并留在那里。他停止移动。

由于禁止迟到，Bruno 必须以最少的行动次数移动到聚会地点。因此，根据本任务的设定，Bruno 永远不会进入与海洋相邻的单元格。

由于在旗帜上写大整数很麻烦，Anna 希望最小化旗帜上所写整数的最大值。

编写一个程序来实现 Anna 的策略和 Bruno 的策略。Anna 将在旗帜上写下整数，Bruno 必须以最少的行动次数到达聚会地点。

实现细节

你需要提交两个文件。 第一个文件是 Anna.cpp。它应该实现 Anna 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 Anna.h。

• void Anna(int N, int K, std::vector<int> R, std::vector<int> C) 此函数实现 Anna 在旗帜上书写整数的策略。对于每个场景（参见“评分”），此函数在开始时恰好被调用一次。
  • 参数 $N$ 表示 JOI 王国的土地是一个由 $N$ 行 $N$ 列方格组成的网格。
  • 参数 $K$ 是聚会候选地点的数量 $K (= 7)$。
  • 参数 $R$ 和 $C$ 是长度为 $K$ 的数组。这里 $R[i]$ 和 $C[i]$ ($0 \le i \le K - 1$) 表示候选地点 $i$ 的单元格 $(R_i, C_i)$。
  • 关于参数 $N, K, R[i]$ 和 $C[i]$ ($0 \le i \le K - 1$) 的取值范围，请参见“数据范围”。

对于每次对 Anna 的函数调用，以下函数必须被调用恰好 $N^2$ 次。它应该为每个单元格调用一次。

• void SetFlag(int r, int c, int value)
  • 参数 $r$ 和 $c$ 表示 Anna 在单元格 $(r, c)$ 的旗帜上写下一个整数。这里应满足 $0 \le r \le N - 1, 0 \le c \le N - 1$。如果不满足此条件，你的程序将被判为 Wrong Answer [1]。
  • 参数 value 是 Anna 在旗帜上写的整数。这里应满足 $1 \le \text{value} \le 1\,000\,000\,000$。如果不满足此条件，你的程序将被判为 Wrong Answer [2]。
  • 如果函数 SetFlag 对相同的参数 $(r, c)$ 调用超过一次，你的程序将被判为 Wrong Answer [3]。
  • 当函数 Anna 终止时，如果对函数 SetFlag 的调用次数不等于 $N^2$，你的程序将被判为 Wrong Answer [4]。

当对函数 SetFlag 的调用被视为 Wrong Answer 时，你的程序将立即终止。

第二个文件是 Bruno.cpp。它应该实现 Bruno 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 Bruno.h。

• std::vector<int> Bruno(int K, std::vector<int> value) 此函数应描述 Bruno 的下一步行动。对于每个场景（参见“评分”），在调用函数 Anna 后，此函数被调用恰好一次。
  • 参数 $K$ 是候选地点的数量 $K (= 7)$。
  • 参数 value 是一个长度为 9 的数组。它包含 Bruno 当前单元格及其周围 8 个单元格旗帜上所写的整数。更准确地说，如果 Bruno 当前在单元格 $(a, b)$ ($1 \le a \le N - 2, 1 \le b \le N - 2$)，则 value[0], value[1], ..., value[8] 分别是以下单元格旗帜上所写的整数： $(a - 1, b - 1), (a - 1, b), (a - 1, b + 1), (a, b - 1), (a, b), (a, b + 1), (a + 1, b - 1), (a + 1, b), (a + 1, b + 1)$
  • 对于每个 $t = 0, 1, 2, \dots, K - 1$，函数 Bruno 应确定当聚会在候选地点 $t$ 举行时 Bruno 的下一步行动。返回值是一个长度为 $K$ 的数组。数组的第 $(i + 1)$ 个元素 ($0 \le i \le K - 1$) 应为 $t = i$ 时 Bruno 的下一步行动。
  • 如果返回值不是长度为 $K$ 的数组，你的程序将被判为 Wrong Answer [5]。
  • 数组中的每个元素都应为 $0, 1, 2, 3$ 或 $4$ 之一。如果不满足此条件，你的程序将被判为 Wrong Answer [6]。
  • 对于每个 $t$，函数 Bruno 给出的行动应该是 Bruno 的下一步行动，以便他以最少的行动次数移动到聚会地点。特别地，如果他的下一步行动是行动 4，他当前的单元格应该是聚会地点。如果不满足此条件，你的程序将被判为 Wrong Answer [7]。如果有多种以最少行动次数移动到聚会地点的方法，返回值可以是其中任何一种。

在本任务中，每个测试用例包含 $Q$ 个场景。对于每个场景，函数 Anna 和函数 Bruno 各被调用恰好一次。因此，对于每个测试用例，函数 Anna 和函数 Bruno 各被调用 $Q$ 次。这些函数交替调用。详见“评分”。

重要提示

• 你的程序可以实现其他内部函数或使用全局变量。提交的文件将与评测器一起编译，并成为一个单一的可执行文件。所有全局变量和内部函数都应在匿名命名空间中声明，以避免与其他文件冲突。在评测时，它将作为 Anna 和 Bruno 的两个进程执行。Anna 的进程和 Bruno 的进程不能共享全局变量。
• 你的程序不得使用标准输入和标准输出。你的程序不得以任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。

评分

每个测试用例包含 $Q$ 个场景。场景编号从 $0$ 到 $Q - 1$。对于每个场景，以下值是固定的。关于这些值的范围，请参见“数据范围”。

• JOI 王国的垂直和水平大小 $N$。
• 候选地点的数量 $K (= 7)$。
• 聚会候选地点 $(R_0, C_0), (R_1, C_1), \dots, (R_{K-1}, C_{K-1})$。
• Bruno 的当前单元格 $(a, b)$。

函数 Anna 对每个场景调用。对于给定的参数，Anna 应该在旗帜上写下整数。函数 Bruno 也对每个场景调用。它应该确定 Bruno 的下一步行动。函数 Anna 和函数 Bruno 的调用方式如下：

1. 对于每个 $k = 0, 1, 2, \dots, Q - 1$，按顺序执行以下 2 和 3。
2. 调用函数 Anna。场景 $k$ 的参数如“实现细节”中所述。
3. 调用函数 Bruno。场景 $k$ 的参数如“实现细节”中所述。

如果你的程序在此过程中被判为 Wrong Answer，你的程序将立即终止，并被视为该测试用例的 Wrong Answer。

数据范围

• $1 \le Q \le 300$
• $5 \le N \le 100$
• $K = 7$
• $1 \le R_i \le N - 2$ ($0 \le i \le K - 1$)
• $1 \le C_i \le N - 2$ ($0 \le i \le K - 1$)
• $(R_i, C_i) \neq (R_j, C_j)$ ($0 \le i < j \le K - 1$)
• $1 \le a \le N - 2$
• $1 \le b \le N - 2$

评分

如果你的程序在任何测试用例中被判为 Wrong Answer，则该任务得分为 0 分。 如果你的程序在每个测试用例中都被判为正确，则该任务的得分计算如下。设 $L$ 为所有测试用例中旗帜上所写整数的最大值。

• 如果 $70\,001 \le L \le 1\,000\,000\,000$，得分为 7 分。
• 如果 $10\,001 \le L \le 70\,000$，得分为 13 分。
• 如果 $2\,001 \le L \le 10\,000$，得分为 19 分。
• 如果 $21 \le L \le 2\,000$，得分为 $50 - 12.5 \times \log_{10} \left( \frac{L}{20} \right)$ 分，向下取整到最接近的整数。

如果 $L \le 20$，得分如下表所示：

样例

输入格式 1

1
5 7
1 1
1 2
2 1
2 2
2 3
3 2
3 3
1 1

输出格式 1

(由评测器输出)

说明

在上述示例中，Anna 在 25 个旗帜上书写的整数如下表所示：

样例通信

在上述样例中，$(a, b) = (1, 1)$。当聚会在候选地点 0, 1, 2 或 3 举行时，Bruno 的下一步行动应如下，函数 Bruno 应返回相应的行动： 如果选择候选地点 0，聚会地点为 $(1, 1)$，Bruno 必须采取行动 4。 如果选择候选地点 1，聚会地点为 $(1, 2)$，Bruno 必须采取行动 0。 如果选择候选地点 2，聚会地点为 $(2, 1)$，Bruno 必须采取行动 2。 如果选择候选地点 3，聚会地点为 $(2, 2)$，Bruno 必须采取行动 0 或行动 2。

在此样例通信中，返回值为 [4,0,2,2,2,0,0]。以最少行动次数移动到聚会地点的方法可能有多种。例如，如果返回值为 [4,0,2,0,2,0,2]，你的程序同样会被判定为正确。

输入格式 2

1
100 7
3 21
16 9
44 36
44 78
45 78
67 59
90 22
84 59

输出格式 2

(由评测器输出)

说明

在此样例输入中，如果函数 Bruno 的返回值为 [3,1,1,0,0,3,2]，则你的程序被判定为正确。