这是一个交互式任务。注意，此任务仅支持 C++。

Benson 兔子的飞机被有毒细菌占领了，他必须去调查！

Benson 兔子有 $n$ 种细菌。每种细菌恰好属于以下 3 种类型之一：普通（Regular）、强壮（Strong）、有毒（Toxic）。其中有 $t$ 种是有毒的。保证至少有 1 种有毒细菌，即 $t \ge 1$。注意，Benson 不知道 $t$ 的值。

Benson 想要识别每种细菌的类型。为了分析细菌，他可以将细菌样本放入一台机器中。他可以指定每种细菌的数量，并可以在机器中添加任意数量的每种细菌，包括 0。这构成了一个样本。由于尺寸限制，样本中的细菌总数不能超过 300。

这 3 种细菌具有以下特性： 如果样本中没有有毒细菌，普通细菌会存活；如果样本中至少有一种有毒细菌，普通细菌就会死亡。 强壮细菌总是会存活。 * 有毒细菌会产生一种毒素，杀死样本中所有非强壮细菌。有毒细菌总是会死亡。

选择样本后，机器会告诉 Benson 总共有多少细菌存活。每次使用机器都需要时间，而 Benson 的时间有限。他最多只能使用机器 600 次。请帮助 Benson 尽可能少地使用样本来确定每种细菌是普通、强壮还是有毒。

实现细节

这是一个交互式任务。不要从标准输入读取或向标准输出写入。

你需要实现以下函数：

• void determine_type(int n)

该函数在每个测试用例中最多会被调用 100 次。每次调用可能包含不同组合的普通、强壮和有毒细菌。对于每个测试用例，你必须在时间和内存限制内解决对该函数的所有调用。

你可以调用以下评测库函数来完成任务：

• int query_sample(std::vector<int> species)
• void answer_type(int x, char c)

函数 query_sample 的参数是一个一维数组 species，描述了你程序选择的样本中每种细菌的种类。species 的大小不能超过 300。此外，传递给 query_sample 的数组不会被修改。换句话说，你可以预期在调用 query_sample 后数组 species 保持不变。

函数 answer_type 接收一个整数 x 和一个字符 c。当你的程序确定种类 x 的细菌类型为 c 时，可以调用此函数。c 可以是 'R'、'S' 或 'T'，分别代表普通、强壮和有毒细菌类型。你的程序必须为所有种类的细菌调用此函数。

以下情况将导致你收到 Wrong Answer 判决并使程序立即终止： 如果 query_sample 或 answer_type 使用了无效参数调用。 如果 answer_type 错误地识别了细菌类型。 如果在 determine_type 终止时，并非所有 $n$ 种细菌都已通过 answer_type 函数识别。 如果在一次 determine_type 调用期间，query_sample 被调用超过 600 次。

请注意，此任务的评测库不是自适应的。这意味着每个测试用例的答案是固定的，并且在程序执行期间不会改变。

样例

假设 $n = 5$。细菌种类 1 和 2 是有毒的，细菌种类 3 和 4 是普通的，细菌种类 5 是强壮的。这对应于字符串 TTRRS。

你的函数将被调用： determine_type(5)

可能的交互过程如下：

• query_sample([1,2,3,4,5]) = 1 此查询中使用了每种细菌的一个样本。只有细菌 5 存活，因此评测库返回 1。

• query_sample([3,3,4,5]) = 4 此查询中使用了两个细菌种类 3 的样本，以及一个细菌种类 4 和 5 的样本。由于没有有毒细菌，所有样本都存活，评测库返回 4。

此时，程序决定它有足够的信息来确定每种细菌的类型，并进行以下 5 次调用：

• answer_type(1,'T')
• answer_type(2,'T')
• answer_type(3,'R')
• answer_type(4,'R')
• answer_type(5,'S')

这些调用均不返回任何值。由于程序已正确识别了所有 $n = 5$ 种细菌类型且使用的查询次数不超过 600 次，因此该测试用例将被视为正确。

请注意，此样例测试用例不满足下方的输入限制。它仅用于测试目的，不需要解决即可获得此任务的满分。

数据范围

你的程序将在满足以下限制的输入实例上进行测试： $n = 300$ $1 \le t \le 30$

此任务的得分取决于你在所有测试用例中对 determine_type 的所有调用所使用的最大查询次数，我们在此将其记为 $m$。

• 如果 $m > 600$，得分为 0。
• 如果 $340 < m \le 600$，得分为 $2 + 7 \times \frac{600-m}{260}$。
• 如果 $275 < m \le 340$，得分为 $9 + 15 \times \frac{340-m}{65}$。
• 如果 $190 < m \le 275$，得分为 $24 + 22 \times \frac{275-m}{85}$。
• 如果 $150 < m \le 190$，得分为 $46 + 54 \times \frac{190-m}{40}$。
• 如果 $m \le 150$，得分为 100。

测试

你可以从附件中下载评测库文件、头文件和解决方案模板。提供了两个输入文件供你测试，sample1.txt 对应于样例交互中的测试用例，sample2.txt 包含一个 $tc = 100$ 且 $n = 300$ 的测试用例。请使用脚本 compile.sh 来编译并运行你的解决方案进行测试。

测试输入格式

第一行包含两个整数 $tc$ 和 $n$。$tc$ 是调用 determine_type 的次数。 接下来的 $tc$ 行，每行包含一个长度为 $n$ 的字符串（R、S 或 T），按顺序描述所有细菌种类的类型。

测试输出格式

每次调用 determine_type 的结果表示为一个整数，打印在新的一行上。

如果你的程序进入了触发 Wrong Answer 判决的任何情况，评测库将输出 -1 并立即终止。剩余的 determine_type 调用将不会执行。

否则，评测库将输出对 query_sample 的调用次数。