Димаш узнал, что Мансур написал про него что-то очень нехорошее своему знакомому, поэтому он решил во что бы ни стало узнать его пароль и узнать, что же именно он написал.
Поверив в силу своего пароля, Мансур сообщил, что его пароль — это бинарная строка размера \(n\). А также он готов отвечать на вопросы Димаша следующего вида:
Димаш говорит бинарную строку \(t\), и Мансур отвечает, правда ли, что \(t\) является подстрокой его пароля.
Помогите Димашу узнать пароль не более чем за \(2n\) операций, иначе Мансур поймет подвох и перестанет с ним общаться.
Протокол взаимодействия
В начале каждого набора входных данных вначале прочитайте \(n\) (\(1 \le n \le 100\)) — размер бинарной строки. Затем приступайте к ее угадыванию.
Для угадывания каждой строки \(s\) вы можете сделать не более \(2n\) запросов следующего вида:
- «? t», где \(t\) — бинарная строка, где (\(1 \le |t| \le n\)).
В ответ на этот запрос вы получите \(1\), если \(t\) является подстрокой \(s\), и \(0\) в противном случае.
Когда вы узнаете ответ, выведите одну строку следующего формата:
- «! s», где \(s\) — бинарная строка размера \(n\).
После этого переходите к решению следующего набора входных данных.
Если вы сделаете некорректную попытку или превысите лимит в \(2n\) попыток, вы считаете \(-1\) вместо ответа и получите вердикт Неправильный ответ. В таком случае ваша программа должна немедленно завершиться, чтобы избежать неопределенных вердиктов.
После вывода запросов не забудьте выводить символ перевода строки и сбрасывать буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы:
Для взломов используйте следующий формат:
Первая строка должна содержать одно целое число \(t\) (\(1\le t\le 100\)) — количество наборов входных данных.
Первая строка каждого набора должна содержать одно число \(n\) (\(1 \le n \le 100\)) — длину строки. А вторая строка должна содержать бинарную строку размера \(n\).
Примечание
В первом примере задана строка \(010\). Поэтому ответы на запросы следующие:
«? 00» \(00\) не является подстрокой \(010\), поэтому ответ \(0\).
«? 000» \(000\) не является подстрокой, поэтому ответ \(0\).
«? 010» \(010\) является подстрокой, поэтому ответ \(1\).
Во втором примере задана строка \(1100\), в третьем \(0110\), а в четвертом \(10\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
0
0
1
4
4
2
|
? 00
? 000
? 010
! 010
! 1100
! 0110
! 10
|