Это интерактивная задача.

Пройдя последний уровень зачарованного храма, вы получили могущественный артефакт 255-го уровня. Не стоит спешить радоваться, ведь на данном артефакте установлена мощная руна, которую можно разрушить единственным секретным заклинанием $$$s$$$. Именно это заклинание вам и предстоит найти.

Определим заклинание как некоторую непустую строку, состоящую только из букв a и b.

В любой момент времени Вы можете произнести произвольное непустое заклинание $$$t$$$, при этом руна на артефакте начнёт сопротивляться. Сопротивлением руны называется редакционное расстояние между строками, задающих произнесённое заклинание $$$t$$$ и искомое секретное заклинание $$$s$$$, при произнесении которого руна разрушается.

Редакционным расстоянием двух строк $$$s$$$ и $$$t$$$ называется величина, равная минимальному количеству односимвольных операций замены, вставки и удаления символов в $$$s$$$ для получения $$$t$$$. К примеру, расстояние между ababa и aaa равно $$$2$$$, aaa и aba — $$$1$$$, bbaba и abb — $$$3$$$. Редакционное расстояние равно $$$0$$$ тогда и только тогда, когда строки равны.

Также стоит учитывать, что у артефакта есть предел сопротивляемости — если вы произнесёте более чем $$$n + 2$$$ заклинаний, где $$$n$$$ — это длина заклинания $$$s$$$, то руна заблокируется.

Таким образом, требуется за $$$n + 2$$$ или меньшее количество заклинаний разрушить руну, находящуюся на Вашем артефакте. Следует учитывать, что искомое разрушающее заклинание $$$s$$$ также должно быть учтено среди этих $$$n + 2$$$ заклинаний.

Учтите, что длина $$$n$$$ разрушающего руну заклинания $$$s$$$ вам заранее не известна. Известно только то, что его длина $$$n$$$ не превосходит $$$300$$$.

Взаимодействие происходит с помощью запросов.

Каждый запрос состоит из единственной непустой строки $$$t$$$ — заклинания, которое вы хотите произнести. Длина строки $$$t$$$ не должна превышать $$$300$$$. Строка должна состоять только из букв a и b.

В ответ на запрос вы получите сопротивление руны — редакционное расстояние между строками, задающих произнесённое заклинание $$$t$$$ и искомое заклинание $$$s$$$, при произнесении которого руна разрушается. Помните, что $$$s$$$ содержит только буквы a и b.

После разрушения руны ваша программа должна немедленно завершиться. Руна разрушается, если её сопротивление достигает значения $$$0$$$. После получения значения $$$0$$$ ваша программа должна завершиться штатным образом.

В этой задаче интерактор не адаптивный. Это означает, что в рамках одного теста искомое заклинание $$$s$$$ не меняется.

При некорректном запросе будет выведено -1. При получении данного значения ваша программа должна немедленно завершиться штатным образом (к примеру, с помощью вызова exit(0)), иначе тестирующая система может выдать произвольный вердикт.

При превышении количества заклинаний (то есть числа $$$n + 2$$$, где $$$n$$$ — длина заклинания $$$s$$$, это число вам неизвестно) будет выведен вердикт неправильный ответ.

Ваше решение может получить вердикт Решение «зависло», если вы ничего не выведете или забудете сбросить буфер вывода.

Чтобы сбросить буфер вывода вам нужно сделать следующее сразу после вывода запроса и символа конца строки:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• см. документацию других языков.

Взломы

Используйте следующий формат для взломов:

В единственной строке выведите строку $$$s$$$ ($$$1 \le |s| \le 300$$$) из букв a и b, задающую разрушающее заклинание.

Взламываемое решение не будет иметь прямого доступа к загаданной строке.