在 Adam 的学校里，新冠疫情出现了新一波的爆发。为了防止进一步传播，学校决定使用抗原检测对所有学生的唾液样本进行检测。

由于所有的老师很久以前就忘记了如何使用这些检测工具，Adam 自愿报名协助进行检测。

他收到了来自 $N$ 名学生的唾液样本（出于隐私原因，他只被允许知道 $0$ 到 $N-1$ 的标识符），他的任务是确定哪些样本呈阳性。不幸的是，当他意识到逐个检测所有学生是一个极其漫长且枯燥的任务时，已经太晚了。然而，他意识到他可以采用比逐个检测样本更聪明的方法。如果他混合一部分样本并对该混合样本进行检测，他就能找出该混合样本中的所有样本是否均为阴性，或者其中至少有一个样本呈阳性。他可以利用这一点来减少他需要进行的检测次数！

由于每个样本的唾液量充足，他可以根据需要多次检测同一个样本。此外，检测结果绝对精确，因此不会出现对同一个样本进行不同检测产生不同结果的情况。

在这些条件下，他希望优化流程，以尽可能减少检测次数。然而，他忙于检测工作，因此流程的优化取决于你。

根据当地统计数据，Adam 能够算出任何给定样本呈阳性的概率等于 $P$，并且一个样本呈阳性或阴性不受其他任何样本的阳性或阴性影响。也许你可以利用这一点来优化他执行的检测？

交互

本题为交互题。

你的程序将在多个测试用例上执行。作为单个测试用例的一部分，因此在你的程序的一次运行中，你将需要解决 $T$ 个不同的场景。$N$ 和 $P$ 的值在所有场景中都是相同的，但哪些学生的样本呈阳性在每个场景中（很可能）是不同的。

你可以自行实现所需的协议，或者使用提供的模板。你可以在 CMS 中找到名为 template.cpp 的任务附件。

协议

首先，你的程序应从标准输入读取一行，包含一个整数 $N$、一个实数 $P$ 和一个整数 $T$，以空格分隔——分别代表学生人数、样本呈阳性的概率和场景数量。

之后，程序可以向标准输出打印查询。每个查询应为单行，包含 Q、一个空格和一个长度为 $N$ 的字符串 $s$，其中如果 Adam 应该将第 $i$ 个学生的样本加入检测，则 $s_i$ 为 1，否则为 0。打印此行后，程序应刷新标准输出，然后读取单行上的一个字符，如果测试组中至少有一个样本呈阳性，则该字符为 P，否则为 N。

程序也可以向标准输出打印答案，格式为单行，包含 A、一个空格和一个长度为 $N$ 的字符串 $s$，其中如果第 $i$ 个学生的样本呈阳性，则 $s_i$ 为 1，否则为 0。打印此行后，程序应刷新标准输出，然后读取单行上的一个字符。

如果该行包含 C，则说明你的答案正确。在这种情况下，程序可以开始执行关于下一个场景的查询，或者如果这是你的第 $T$ 个答案，则退出。

如果该行包含 W，则说明你的答案不正确。在这种情况下，程序应立即退出。

请注意，在收到 W 后退出对于从 CMS 获取正确的反馈很重要。如果你的程序继续运行，它可能会崩溃或收到其他不成功的判决。

模板

如果你使用 template.cpp 中的协议实现，你需要实现函数 std::vector<bool> find_positive()。该函数将为每个场景调用一次。它必须返回一个长度为 $N$ 的布尔向量，其中第 $i$ 个元素为 true 当且仅当第 $i$ 个学生的样本呈阳性。

为此，你可以使用函数 bool test_students(std::vector<bool> mask)。该函数对样本的子集执行检测。其唯一参数是一个长度为 $N$ 的布尔向量，其中第 $i$ 个元素为 true 表示第 $i$ 个样本应加入混合样本。如果（且仅当）混合样本中至少有一个样本呈阳性，它返回 true。

你还可以使用全局变量 N 和 P，它们包含题目中的 $N$ 和 $P$。你可以在第一次调用 scanf 后的 main 函数中进行任何初始化。

输入格式

本题的评测机是非自适应的，这意味着单个样本的阳性情况在运行你的程序之前就已经确定。此外，任何给定样本是否呈阳性是使用公平随机数生成器以概率 $P$ 独立确定的。

子任务与评分

本题有两个子任务。

子任务 1（10 分）

• $N = 1000$
• $T = 1$
• $0 \le P \le 1$

如果方案回答正确且在每个测试用例上最多使用 $2 \cdot N$ 次查询，则该方案被接受。

子任务 2（90 分）

• $N = 1000$
• $T = 300$
• $0.001 \le P \le 0.2$

该子任务使用部分评分。

如果你的答案在任何场景中错误，你将获得零分。否则，给定测试用例的得分将根据每个场景的平均查询次数确定。通常，较少的查询次数会产生较高的分数。令 $Q$ 表示你的程序在所有场景中使用的平均查询次数，向下取整到小数点后一位。对于每个测试用例，我们计算了一个值 $F$（见下文）。给定测试用例的得分将根据以下规则计算：

• 如果 $Q > 10 \cdot F$，你将获得 0 分（答案错误）。
• 如果 $F < Q \le 10 \cdot F$，分数将由以下公式确定： $$90 \cdot \frac{F}{F + 4 \cdot (Q - F)}$$
• 如果 $Q \le F$，你将获得满分 90 分。

你的方案将在具有不同 $P$ 值的多个测试用例上进行评分。你将获得的最终总分将是所有测试用例中的最低得分（即，跨越所有概率 $P$）。

存在以下测试用例：

评测系统将为每个测试用例提供反馈。此反馈将包括你在获得非零分数的每个测试用例上方案的 $Q$ 值。

样例

样例交互 1

10 0.4 2
Q 1000000000
P
Q 0000001000
P
Q 0000000001
P
Q 0111110110
N
A 1000001001
C
A 0000000000
W

该程序正确解决了第一个场景，但没有解决第二个场景，因为正确答案是 1100010010（程序无法知道这一点，因为它没有执行任何查询）。即使还有另一个场景，程序也应立即终止。