题目背景

$\clubsuit$ 星球盛产“代马”，其优越的速度与耗能使得它风靡整个银河系。可小 $\iiint$ 并不满足于此，他想培育出更好的“代马”，并取代掉还在用传统能源的落后四足兽。于是，他开始研究基因技术……

本题仅支持 C++ 语言提交。

由于技术限制，请勿使用 C++14 (GCC 9) 语言提交，否则将会得到 Compile Error 的结果。

你的代码中需如下进行 query 和 cross 函数的声明：

char query(int k);
void cross(int i, int j);

调用 $10^6$ 次 query 与 cross 函数的时间不超过 50 毫秒，除这两个函数所占用的时间外，交互库运行所占用的时间不超过 100 毫秒。

题目描述

【形式化题意】

这是一道交互题。

定义 基因 为一个字符，其内容为 $\verb!A!$ 或 $\verb!a!$。定义 基因型 为由两个基因组成，且大写字母在小写字母之前的字符串。也即 $\{\verb!aa!,\verb!Aa!,\verb!AA!\}$ 中的一种。一个基因型的 表现 如下：

• 若基因型中含有 $\verb!A!$，则表现为 $\verb!A!$。
• 否则，表现为 $\verb!a!$。

两个基因型可以相互 杂交，其定义如下：

• 在两个基因型中各均匀随机取一个基因，并将两个基因组合成基因型作为结果输出。

小 $\iiint$ 有 $n$ 个基因型，编号为 $1,2,\cdots,n$。每次询问可以给交互库两个不同的编号 $i,j$。若当前是第 $k$ 次杂交，交互库会新建一个编号为 $n+k$ 的基因型，其基因型为 $i,j$ 杂交后的结果。

你可以在时限范围内任意次查询编号为 $x$ 的种子的表现。你需要在 $4.5\times10^5$ 次杂交内，求出初始给定的 $n$ 个基因型。

实现细节

你不需要，也不应该实现主函数。 你需要实现下面的函数：

vector<string> guess(int n)

• $n$ 表示初始基因型个数。
• 该函数应当返回一个长度恰好为 $n$ 的数组，数组中的每一个元素是一个长度为二的字符串，表示你所求出的基因型。你需要保证大写字母在小写字母的前面。
• 对于每个测试点，该函数被恰好调用一次。

该函数可调用以下函数：

char query(int k)

• $k$ 表示你要查询的基因型的编号。你需要保证这个编号对应的基因型存在。
• 该函数将返回该基因型的表现。
• 该函数可以在时限内被调用任意次。

void cross(int i, int j)

• $i,j$ 代表你要杂交的两个基因的编号。你需要保证 $i\not=j$ 且对应的基因型存在。
• 若是第 $k$ 次调用该函数，该函数会新建一个编号为 $n+k$ 的基因型，其基因型为 $i,j$ 杂交后的结果。保证杂交过程为均匀随机。
• 你最多可以调用该函数 $4.5\times10^5$ 次。
• 评测程序不是适应性的。也就是说，所有初始元素的基因型在 guess 函数被调用前已经确定。

提示

【交互示例】

以下为 $n=2$，基因型为 $\{\verb!Aa!,\verb!AA!\}$ 时一种可能的交互过程。

选手程序	交互库
	guess(2)
cross(1,2)
	$\{\verb!Aa!,\verb!AA!,\verb!Aa!\}$
cross(1,3)
	$\{\verb!Aa!,\verb!AA!,\verb!Aa!,\verb!aa!\}$
query(4)
	$\verb!a!$
$\{\verb!Aa!,\verb!AA!\}$
	Ok,accepted.

【约束条件】

• $2\le n\le 2\times10^4$，$n$ 为偶数。
• 每次程序运行时将恰好调用一次 guess() 函数。
• 保证交互库是非自适应性的，即所有初始元素的基因型不在交互过程中发生改变。

【子任务】

Subtask	分值	$n\le$	特殊性质
$0$		$2$	无
$1$	$5$	$2\times10^4$	保证不存在 $\verb!Aa!$
$2$	$15$	$500$	无
$3$	$20$	$2\times10^4$	保证至少存在一个 $\verb!aa!$
$4$	$25$	$5\times10^3$	无
$5$	$35$	$2\times10^4$

对于所有数据，$2\le n\le 2\times10^4$，保证 $n$ 为偶数。

由于本题涉及概率与期望，如果你确定你的算法无误，可以尝试多交几发。