Самое сложное испытание для учеников школы занимательной математики, в которой учится Вася — итоговая контрольная по цифровым сдвигам. Каждый год задачи по этому предмету становятся все сложнее, и в этот раз учитель математики Цифрский подготовил нечто невероятное.

Десятичная запись некоторого числа начинается с группы цифр, которую мы обозначим B. Другими словами, исходное число имеет вид BX. Если умножить это число на A, то результатом умножения станет число, получаемое переписыванием группы цифр B из начала в конец исходного числа, то есть итог умножения имеет вид XB.

Задача Васи — найти минимально возможное исходное число BX по заданным A и B. Помогите ему справиться с этой нелегкой задачей.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Вася и Антивася играют в кольца.

У Васи в руках матрица цифр размером N строк и M столбцов. Вася должен разрезать матрицу на столбцы, выбрать порядок их следования и, не разворачивая, склеить в одну длинную ленту. Затем ленту следует склеить в кольцо и вновь разрезать в произвольном месте таким образом, чтобы на ленте сверху вниз можно было прочесть максимально возможное число.

В руках Антиваси идентичная матрица, однако он действует иначе. Его задача — разрезать матрицу на строки, выбрать порядок их следования и, не разворачивая, склеить в одну длинную ленту. Затем Антивася должен склеить ленту в кольцо и вновь разрезать в произвольном месте таким образом, чтобы на ленте слева направо можно было прочесть максимально возможное число.

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Одна из любимых тем Васи — системы счисления. И на днях ему попалось описание синонимичной системы счисления слов (СССС).

Синонимичная система счисления слов (СССС) оперирует строками из N символов «0» и «1» (2 ≤ N ≤ 10000). В рамках данной системы счисления существует единственная операция над словами — синонимизация. Синонимизацией называется замена порядка символов в любой подстроке слова, количество единиц в которой четно, на обратный.

Если из одного слова можно получить другое, совершив не более 16·N синонимизаций, то такие слова называются синонимами.

Васе необходимо выяснить, являются ли заданные слова синонимами, и, если являются, привести подходящую последовательность синонимизаций.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

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

Окутанный фантасмагоричными предзнаменованиями Вася взирает на безлунное небо. «Если бы я мог стать столь же чрезвычайно сияющим» — подумал Вася вглядевшись в звезду, и тут же получил зловещее предупреждение из древних глубин космоса. И тогда он понял, что сосредоточив свое невежественное сознание на некоторых звездах, можно услышать кошмарный зов неизвестного Древнего Бога.

Вспомнив знания, полученные из Некрономикона, Вася установил, что каждый из Древних имеет свой радиус влияния, и звезды находящиеся внутри радиуса отвечают зовом тому, кто в них вглядывается. Три Бога отравляют реальность своим противоестественным существованием: Азазот, с радиусом влияния 30 световых лет, Йог-Сотот с радиусом 20 и Шаб-Ниггурат с радиусом 10. Небо представляет собой координатную плоскость 100 на 100 световых лет, и на каждой целочисленной координате находится звезда. Вася может всматриваться в звезду с определенными координатами и понимать, находится ли она в радиусе влияния Древнего.

В данный момент пробудился только один Древний, то есть только вокруг него звезды отвечают на взор. Вася должен понять, какой из Древних пробудился и сказать его радиус, но сделать все это не более чем за N действий, иначе Вася сойдет с ума от переполняющего чудовищного познания.

Чтобы узнать находится ли звезда (X, Y) внутри зоны влияния Древнего, выведите в стандартный поток строку вида «? X Y», где X, Y — целые числа (0 ≤ X, Y ≤ 100). После этого выведите перевод строки и выполните операцию flush.

В ответ на запрос придет одно целое число: единица, если звезда находится внутри зоны влияния Древнего и ноль, если нет.

Чтобы вывести ответ на задачу, выведите строку вида «! R», где R — радиус влияния пробужденного Древнего.

Если вы сделаете более N запросов вида «? X Y» или сделаете некорректный запрос, решение получит вердикт «Неправильный ответ».

Если в какой-то момент ваша программа ничего не будет выводить или вы забудете выполнить операцию flush после вывода вопроса или ответа, решение получит вердикт «Решение зависло».

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

• fflush(stdout) в C++;
• System.out.flush() в Java;
• stdout.flush() в Python;
• flush(output) в Pascal;

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.