Марк администрирует онлайн-экзамен, состоящий из \(n\) вопросов с ответами «да» или «нет». Однако он потерял список правильных ответов. Ему необходим способ восстановить ответы до того, как его клиент придет в ярость.
К счастью, у него есть доступ к системе оценки. Так, за один запрос вы можете ввести ответы ко всем \(n\) вопросам из экзамена и система оценки ответит, сколько введенных ответов верны.
У Марка есть не так много времени, поэтому он может использовать систему оценки не более \(675\) раз. Помогите Марку определить правильные ответы ко всем вопросам экзамена.
Обратите внимание, что правильные ответы к вопросам фиксированы и не будут меняться в зависимости от ваших запросов.
Протокол взаимодействия
После чтения \(n\) вы можете начинать делать запросы к системе оценки. Чтобы сделать запрос, выведите строку \(s\) длины \(n\), состоящую только из букв «T» и «F».
- \(s_i = \)T означает, что предполагаемый ответ на \(i\)-й вопрос — «да».
- \(s_i = \)F означает, что предполагаемый ответ на \(i\)-й вопрос — «нет».
После успешного запроса вы должны прочитать целое число \(k\) (\(0\leq k\leq n\)) — количество верных ответов. Если вы прочитали \(n\), то вы нашли все ответы, и ваша программа должна завершиться.
Если ваше решение прочитало \(k = -1\) вместо ответа системы оценки, это значит, что вы совершили некорректный запрос или достигли ограничения на количество запросов. Ваша программа должна немедленно завершиться после прочтения ответа \(-1\), вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Для взлома используйте следующий формат.
Первая строка содержит целое число \(n\) (\(1\leq n\leq 1000\)) — количество вопросов.
Вторая строка содержит строку \(s\) длины \(n\), состоящую только из букв «T» и «F» — правильные ответы на экзамене.
Примечание
Пустые строки в примерах нужны только для того, чтобы вы лучше понимали процесс взаимодействия. От вас не требуется их выводить.
В первом примере экзамен состоит из \(3\) вопросов, ответы на которые «да», «да» и «нет» соответственно.
- В первом запросе предполагаются ответы «нет», «да» и «да» соответственно. Верно угадан только один ответ — на \(2\)-й вопрос.
- Затем, во втором запросе, программа верно угадала все ответы.
Во втором примере экзамен состоит из \(4\) вопросов, ответы на которые «да», «нет», «да» и «да» соответственно.
- В первом запросе нет верно угаданных ответов, поэтому ответ от программы жюри \(0\).
- Во втором запросе верно угаданы \(1\)-й, \(3\)-й, и \(4\)-й ответы, поэтому ответ системы \(3\).
- В третьем запросе программа верно угадала все ответы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
3
|
FTT
TTF
|
|
2
|
4
0
3
4
|
FTFF
TTTT
TFTT
|