题目背景

这是一道交互题。

本题只支持 C++ 提交，建议使用 C++17。

提交时不需要包含 toxic.h 头文件。

为了确保程序正常编译，你需要在你提交的程序开头加上如下函数声明语句：

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

如遇评测问题，请联系搬题人。

题目描述

建议仔细区分题面中的“种类”和“个体”。

兔子 Benson 的飞机被有害病毒侵袭了，他必须对此展开调查！

Benson 发现了 $n$ 种病毒，每种病毒恰好属于三个类型之一：普通、强悍和毒害。保证至少有一种毒害病毒。

Benson 必须识别每种病毒的类型。为了分析之，他将使用一个特殊的机器。每一次，他可以选择任意数量的病毒（包括 $0$）制成标本，并将其放入机器中。受机器大小的影响，每个标本里不能有超过 $300$ 个病毒。每个病毒的种类由 Benson 任意指定。

标本放入机器后，其中三个类型的病毒会发生如下反应：

• 当且仅当不存在毒害病毒，普通病毒可以存活。

• 强悍病毒总是存活。

• 毒害病毒产生有害物质并杀死强悍病毒外的所有病毒。因此，毒害病毒总是死亡。

对于每个样本，机器会告诉 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，表示标本中你所选择的病毒种类。该数组的大小不能超过 $300$。此外，你可以假定该函数调用结束后，species 数组不会改变。

调用 answer_type 函数时，需传入一个整数 $x$ 和一个字符 $c$。当你确定第 $x$ 种病毒的类型时，调用该函数，其中 $c$ 是 R、S 或 T 之一，分别表示普通病毒、强悍病毒和毒害病毒。你必须对每种病毒都调用该函数。

下列情况可能导致你收到 Wrong Answer 反馈并立即结束评测：

• query_sample 函数或 answer_type 函数的调用非法
• answer_type 函数给出的病毒种类有误
• determine_type 函数结束时，存在某种病毒未被 answer_type 确认
• 某次 determine_type 函数调用过程中，query_sample 被调用了超过 $600$ 次

请注意，题目中的交互库是非自适应的，即每个测试数据的答案被提前确定，且不会在交互过程中改变。

输入格式

示例测试程序按如下格式读取输入数据：

第一行两个整数 $tc, n$。$tc$ 表示 determine_type 的调用次数。

接下来 $tc$ 行，每行一个字符串，由 R、S 和 T 组成，依次描述每种病毒的类型。

输出格式

示例测试程序按如下格式输出信息：

对于每次 determine_type 的调用，输出一行一个整数：若反馈为 Wrong Answer，输出 $-1$；否则输出 query_sample 的调用次数。

提示

调用示例

假定 $n=5$，第一种病毒和第二种病毒是毒害病毒，第三种病毒和第四种病毒是普通病毒，第五种病毒是强悍病毒。该情况可用字符串 TTRRS 表达。

你的函数会被这样调用：

• determine_type(5)

一个可能的交互过程如下：

• query_sample([1,2,3,4,5]) = 1 所有种类的病毒都被放置在标本中，只有种类 $5$ 的病毒存活，故返回 $1$。

• query_sample([3,3,4,5]) = 4 两个“第三种病毒”、一个“第四种病毒”和一个“第五种病毒”被放置在标本中。由于不存在毒害病毒，所有病毒均存活，故返回 $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$ 次询问时，会在该测试点中被认为是正确的。

请注意，该示例仅供展示交互过程，不一定存在合理逻辑。

得分细则

设 $t$ 表示毒害病毒的数量。保证测试数据中 $n=300$，$1\leq t\leq 30$。

某测试点中，你的得分与所有 determine_type 调用中，询问次数的最大值有关，设为 $m$。

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

程序测试

下发文件中有两个数据可供测试。sample1.txt 是上文的【调用示例】，sample2.txt 中含有一组 $tc=100,n=300$ 的测试数据。请使用 compile.sh 编译并运行你的程序。