Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Mark and the Online Exam

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMark is administering an online exam consisting of $$$n$$$ true-false questions. However, he has lost all answer keys. He needs a way to retrieve the answers before his client gets infuriated.

Fortunately, he has access to the grading system. Thus, for each query, you can input the answers to all $$$n$$$ questions, and the grading system will output how many of them are correct.

He doesn't have much time, so he can use the grading system at most $$$675$$$ times. Help Mark determine the answer keys.

Note that answer keys are fixed in advance and will not change depending on your queries.

Input

The first line of the input consists of an integer $$$n$$$ ($$$1\leq n\leq 1000$$$) — the number of questions.

Interaction

After reading $$$n$$$, you can start making queries to the grading system. For each query, print a line containing a string $$$s$$$ of length $$$n$$$ consisting of only letters 'T' and 'F'.

- $$$s_i = $$$'T' means that you answer the $$$i$$$-question true.
- $$$s_i = $$$'F' means that you answer the $$$i$$$-question false.

After a successful query, you should read an integer $$$k$$$ ($$$0\leq k\leq n$$$) — the number of correct answers. If you read $$$n$$$, then you found the answers, and your program should not make any more queries.

If your program reads $$$k = -1$$$ instead of the number of correct answers, it means that you either made an invalid query or exceeded the query limits. Exit immediately after receiving $$$-1$$$, and you will see Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hacks

To hack, use the following format:

The first line contains an integer $$$n$$$ ($$$1\leq n\leq 1000$$$) — the number of questions.

The second line contains a string $$$s$$$ of length $$$n$$$ consisting of only 'T' and 'F' — the answer key.

Examples

Input

3 1 3

Output

FTT TTF

Input

4 0 3 4

Output

FTFF TTTT TFTT

Note

The empty lines in the example are just for you to better understand the interaction process. You're not required to print them.

In the first example, there are $$$3$$$ questions, and the answer to each question is 'true', 'true', and 'false', respectively.

- The first query, guessing the answers to be 'false', 'true', and 'true', respectively, guesses only one question — the $$$2$$$-nd question — correctly.
- Then, in the second query, the program correctly guesses the answer key. The interaction ends here.

In the second example, there are $$$4$$$ questions, and the answer to each question is 'true', 'false', 'true', and 'true', respectively.

- The first query guessed none of the questions correctly, resulting in the answer $$$0$$$.
- The second query guessed the $$$1$$$-st, $$$3$$$-rd, and $$$4$$$-th question correctly, resulting in the answer $$$3$$$.
- In the third query, the program correctly guesses the answer key. Then, the interaction ends.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/07/2023 20:38:20 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|