你在玩一个动作游戏。游戏控制器有 $4$ 个按键，A、B、X 和 Y。在游戏中，你用组合动作来赚金币。你可以依次按这些按键来完成一个组合动作。

这个游戏有一个隐藏的按键序列，可以表示为由这 $4$ 个字符组成的串 $S$。你并不知道这个串 $S$，但是你知道它的长度为 $N$。

你还知道，$S$ 的首字符不会在串中重复出现。例如，$S$ 可以是“ABXYY”或者“XYYAA”，但不能是“AAAAA”或“BXYBX”。

你可以依次按最多 $4N$ 个按键来完成一个组合动作。串 $p$ 为你所按的按键序列。你用这个组合动作赚到的金币数量，等于同时为 $p$ 之子串和 $S$ 之前缀的最长字符串的长度。串 $t$ 的子串定义为 $t$ 中的连续字符序列（可以为空）。$t$ 的前缀定义为 $t$ 的子串，其或者为空，或者包含 $t$ 的首字符。

例如，如果 $S$ 是“ABXYY”，而 $p$ 是“XXYYABYABXAY”，你会得到 $3$ 个金币，因为“ABX”是可作为 $p$ 的子串的 $S$ 的前缀中最长的。

你的任务是，用少量的组合动作，找出隐藏字符串 $S$。

实现细节

你需要实现下面的函数：

std::string guess_sequence(int N)

• N：串 $S$ 的长度。
• 对每个测试用例，该函数被调用恰好一次。
• 该函数应返回串 $S$。

你的程序可以调用下面的函数：

int press(std::string p)

• p：你的按键序列。
• p 必须是长度为从 $0$ 到 $4N$ 的串（包括 $0$ 和 $4N$）。p 的每个字符必须是 A、B、X 或者 Y。
• 对每个测试用例，你调用该函数的次数不能超过 $8000$ 次。
• 该函数的返回结果是，当按出按键序列 p 后你赚到的金币数量。

如果不满足上面的条件，你的程序将被判为 Wrong Answer。否则，你的程序将被判为 Accepted，而你的得分将根据 press 的调用次数来计算（参见子任务）。

例子

设 $S$ 为“ABXYY”。评测程序调用了 guess_sequence(5)。数据交互过程的例子如下所示：

对于 press 的第 $1$ 次调用，“ABX”是“XXYYABYABXAY”的子串，而“ABXY”不是，因此返回 $3$。

对于 press 的第 $3$ 次调用，“ABXYY”本身是“ABXYYABXYY”的子串，因此返回 $5$。

对于 press 的第 $6$ 次调用，除了空串以外没有“ABXYY”的其他前缀可以是“BXYY”的子串，因此返回 $0$。

最后，guess_sequence(5) 应当返回“ABXYY”。

在样例数据下载中的文件ex_combo1.in对应于本例。注意：样例包中的输出没有任何意义。

限制条件

• $1\le N\le 2000$
• 串 $S$ 的每个字符必须是 A、B、X 或 Y。
• $S$ 的首字符不会再 $S$ 中重复出现。

在本题中，评测程序不是适应性的。意思是说，在评测程序开始运行的时候 $S$ 就固定下来，而且不依赖于你的程序所做的询问。

子任务

1. （5分）$N=3$
2. （95分）没有附加限制。对该子任务，你在每个测试用例上的得分将计算如下。设 $q$ 为调用 press 的次数。
   • 如果 $q\le N+2$ ，你的得分为 $95$。
   • 如果 $N+2<q\le N+10$，你的得分为 $95-3(q-N-2)$。
   • 如果 $N+10<q\le 2N+1$，你的得分为 $25$。
   • 如果 $max\{N+10,2N+1\}<q\le 4N$，你的得分为 $5$。
   • 否则，你的得分为 $0$。

注意，你在每个子任务上的得分，等于你在该子任务下所有测试用例上的最低得分。

请注意：在测试中，如果你的程序的询问次数超过 $N+2$，则会得到 $0$ 分。。

评测程序示例

评测程序示例将读取如下格式的输入：

• 第 $1$ 行：$S$

如果你的程序被判为 Accepted，评测系统示例将打印出 Accepted: q，这里 q 为函数 press 的调用次数。

如果你的程序被判为 Wrong Answer，它打印出 Wrong Answer: MSG。各类 MSG 的含义如下：

• invalid press：输入到 press 的值 p 是无效的。也就是说，p 的长度不在 $0$ 到 $4N$ 之间（含 $0$ 和 $4N$），或者 p 的某些字符不是 A、B、X 和 Y。
• too many moves：函数 press 的调用次数超过 $8000$ 次。
• wrong guess：guess_sequence 返回的不是 $S$。

约定及限制

对于所支持的各种编程语言，下面列出了对应的数据类型。对于数据类型的细节等，参见实现示例。

时间限制：$1\mathtt{\text{s}}$

空间限制：$268\mathtt{\text{MB}}$

下载

样例数据下载