Genotype Guessing Interactively

This is an interactive problem.

We define a gene as a character which is either \(A\) or \(a\). A genotype is defined as a string of two genes with the uppercase letter preceding the lowercase letter. That is, a genotype is one of \(\{aa, Aa, AA\}\). The phenotype (i.e. appearance) of a genotype is defined as follows:

• If the genotype contains at least one \(A\), its phenotype is \(A\).
• Otherwise, the phenotype is \(a\).

Two genotypes can be crossed (hybridized) with the following rule:

• For each genotype, one gene is chosen uniformly at random. The two chosen genes form a new genotype (remember to keep the uppercase letter before the lowercase letter).

You are given \(n\) genotypes, numbered \(1, 2, \ldots, n\). In each query, you may provide two distinct indices \(i, j\) to the interactive library. If this is the \(k\)-th cross, the library will create a new genotype with index \(n+k\), whose genotype is the result of crossing genotype \(i\) and genotype \(j\) according to the above rule.

You may query the phenotype of any genotype by calling query(k). You are allowed unlimited queries within the time limit. Your goal is to determine the exact genotype (two-letter string with the uppercase letter before the lowercase letter) of all the initial \(n\) genotypes. You are allowed at most \(4.5 \times 10^5\) cross operations.

Function Specifications

You do not need, and indeed should not, implement the main function. You must implement the following function:

vector<string> guess(int n)

• n is the number of initial genotypes.
• Your function should return an array of exactly \(n\) strings, each of length 2, representing the genotype you determined. Ensure that the uppercase letter comes before the lowercase letter in each output.

You are allowed to call the following functions:

char query(int k);

• k is the genotype index you wish to query. Make sure the genotype with index k exists.
• This function returns the phenotype of the genotype (i.e. \(A\) or \(a\)).

void cross(int i, int j);

• i and j are the indices of the genotypes to cross (\(i \neq j\) and both must exist).
• The \(k\)-th call to cross will create a new genotype with index \(n+k\) whose genes are chosen uniformly at random from the two parent genotypes.
• You may call this function at most \(4.5 \times 10^5\) times.
• The test cases are not adaptive, i.e. all initial genotypes are fixed before guess is called.

Your task is to determine the genotype of each of the initial \(n\) genotypes by making use of the functions provided.

inputFormat

The interactive judge provides an initial integer \(n\) (\(1 \le n \le \text{some limit}\)) and then the secret genotypes for the initial seeds. In our offline simulation, the input consists of an integer \(n\) on the first line, followed by \(n\) lines each containing a two-character string representing the genotype (one of aa, Aa, or AA). You can assume that the two letters are in the correct order (uppercase letter comes before lowercase letter).

outputFormat

Your function should output exactly \(n\) lines, where the \(i\)-th line is the two-character string representing the genotype of the \(i\)-th initial seed.

sample

1
aa

aa

</p>