Virus Type Identification

Note: Carefully differentiate between the "species" and the "individual" in the problem statement.

Rabbit Benson's airplane has been invaded by a harmful virus, and he must investigate it! Benson has discovered \(n\) virus species. Each species is exactly one of three types: normal, strong, or toxic. It is guaranteed that there is at least one toxic virus.

To analyze the viruses, Benson will use a special machine. In each query, he can select an arbitrary number of viruses (possibly 0) from any species to create a sample. Owing to the machine's size, no sample may contain more than \(300\) viruses. For each virus added into the sample, Benson can arbitrarily decide which species it belongs to.

When a sample is processed, the three types of viruses react as follows:

• Normal viruses survive if and only if there is no toxic virus in the sample.
• Strong viruses always survive.
• Toxic viruses produce harmful substances that kill every virus except the strong ones. Thus, toxic viruses always die.

For each sample, the machine reports the number of surviving viruses. However, due to the machine's long analysis time, Benson can use it at most 600 times per test case. Your task is to help Benson determine the type of each virus species: normal, strong, or toxic.

Interaction Details:

This is an interactive problem. You need to implement the following function:

• void determine_type(int n)

For each test case, this function will be called at most 100 times, each call corresponding to a different set of virus species. In each call, you must ensure that you do not exceed the time and space limits.

You can use the following functions:

• int query_sample(std::vector<int> species): When calling this function, you must pass a one-dimensional array species representing the species chosen for the sample. The size of the array cannot exceed \(300\). You can assume that after the function call, the species array remains unchanged.
• void answer_type(int x, char c): When you are sure of the type for the \(x\)-th virus species, call this function with c being one of 'R', 'S', or 'T', representing a normal, strong, or toxic virus respectively. You must call this function for every virus species.

Violations of the following conditions will result in a Wrong Answer verdict and immediate termination of the evaluation:

• Illegal calls to query_sample or answer_type.
• Providing an incorrect virus type in answer_type.
• Not calling answer_type for every virus species before the end of determine_type.
• Calling query_sample more than 600 times in a single invocation of determine_type.

Please note that the interaction library is non-adaptive, i.e. the answers for each test case are determined in advance and will not change during the interaction.

inputFormat

This is an interactive problem; however, for the purpose of offline testing, the input is given as follows:

• The first line contains an integer \(n\) representing the number of virus species.
• The second line contains \(n\) characters (each separated by a space) representing the true type of each virus species. Each character is one of R, S, or T. It is guaranteed that there is at least one T.

Your solution should interact with the provided functions query_sample and answer_type to find out the types. In our offline simulation, you may simply read the input and output the correct types.

outputFormat

In the offline simulation, for each virus species you must output its type (as a character: R, S, or T) in order, separated by a space.

sample

3
R T S

R T S