Mike 正在和 Peter 玩一个游戏。地面上有一排 $n$ 个方格，从左到右编号为 $0$ 到 $n-1$。游戏开始时，Peter 可以将这些方格涂成黑色或白色。然后他会给 Mike 一个正整数 $k$ ($1 \le k \le n$)。
这个游戏总共持续 $q$ 轮。在每一轮中，Mike 会随机选择一个方格 $x$ ($0 \le x < n$)，并告诉 Peter 从位置 $x$ 到 $x+k-1$（包含两端）的方格颜色。如果这些位置中有超出范围的，Mike 也会相应地告知 Peter。Peter 需要仅凭这些信息准确推断出 $x$。
Peter 希望给 Mike 留下深刻印象，因此他想选择尽可能小的 $k$ 值。请帮助 Peter 设计一个策略，以最小的 $k$ 值赢得这个游戏。
实现细节
你需要实现以下过程：
int[] paint(int n)- $n$：方格的数量。
- 该过程应返回一个大小为 $n+1$ 的数组。数组的前 $n$ 个元素应为方格的颜色。如果第 $i$ 个方格被涂成白色，则数组的第 $i$ 个元素应设为 $1$；如果被涂成黑色，则设为 $0$。数组的最后一个元素应为 $k$ 的值。
- 对于每个场景，该过程在调用
find_location之前会被精确调用一次。
int find_location(int n, int c[])- $n$：方格的数量。
- $c$：一个大小为 $k$ 的数组。如果第 $(i+x)$ 个方格被涂成白色，则数组的第 $i$ 个元素设为 $1$；如果被涂成黑色，则设为 $0$。如果第 $(i+x)$ 个方格不存在，则数组的第 $i$ 个元素设为 $-1$。
- 该过程应返回推断出的 $x$ 值。
- 对于每个场景，该过程会被精确调用 $q$ 次，每一轮调用一次。
每个测试用例可能涉及多个独立的场景（即不同的 $n$ 值）。对于涉及 $r$ 个场景的测试用例，调用上述过程的程序会精确运行两次，如下所示：
在程序的第一次运行期间：
paint 过程被调用 $r$ 次，
返回的颜色和 $k$ 值由评分系统存储，并且
* 不调用 find_location。
在程序的第二次运行期间：
find_location 可能会被多次调用，
每次调用 find_location 时给出的 $n$ 和颜色值，都是在第一次运行中针对某个任意选择的场景调用 paint 所产生的结果，
* 不调用 paint。
样例
考虑以下调用：
paint(5)总共有 $5$ 个方格。Peter 可以选择将方格依次涂成黑色、黑色、白色、黑色、白色，并决定 $k=3$ 足以让他推断出 $x$ 的值。在这种情况下，该过程应返回 $[0, 0, 1, 0, 1, 3]$。
随后会进行多次 find_location 调用。
考虑一个可能的调用：
find_location(5, [0, 1, 0])这意味着第 $x$ 个、$(x+1)$ 个和 $(x+2)$ 个方格的颜色分别是黑色、白色和黑色。Peter 可以据此推断出 $x=1$。因此，该过程应返回 $1$。
考虑另一个可能的调用：
find_location(5, [1, 0, 1])这意味着第 $x$ 个、$(x+1)$ 个和 $(x+2)$ 个方格的颜色分别是白色、黑色和白色。Peter 可以据此推断出 $x=2$。因此，该过程应返回 $2$。
数据范围
- $1 \le r \le 10$
- $2 \le n, q \le 1000$
- $-1 \le c[i] \le 1$ ($0 \le i < k$)
子任务
- (10 分)
paint返回的 $k$ 值不超过 $1000$。 - (15 分)
paint返回的 $k$ 值不超过 $100$。 - (20 分)
paint返回的 $k$ 值不超过 $70$。 - (55 分)
paint返回的 $k$ 值不超过 $30$。
在子任务 4 中，你可以获得部分分数。设 $m$ 为所有场景中 paint 返回的 $k$ 值的最大值。该子任务的得分计算如下表所示：
| 最大 $k$ 值 | 得分 |
|---|---|
| $m \ge 30$ | $0$ |
| $10 < m < 30$ | $\frac{30-m}{20} \cdot 55$ |
| $m \le 10$ | $55$ |
样例评测程序
样例评测程序按以下格式读取输入：
- 第 $1$ 行：$r$
随后是 $r$ 个数据块，每个数据块描述一个场景。每个数据块的格式如下：
- 第 $1$ 行：$n \ q$
- 第 $2+i$ 行 ($0 \le i < q$)：第 $i$ 次调用
find_location时的 $x$ 值。
样例评测程序按以下格式输出：
- 第 $1$ 行：$m$
随后是对应输入中连续场景的 $r$ 个数据块。每个数据块的格式如下：
- 第 $1+i$ 行 ($0 \le i < q$)：第 $i$ 次调用
find_location时返回的推断出的 $x$ 值。
注意：样例评测程序的每次运行都会调用 paint 和 find_location。