Задача C. Чёрный ящик

Автор:А. Кленин   Ограничение времени:2 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Данная задача является интерактивной.

Юные программисты Петя и Вася играют в следующую игру. Петя задумывает последовательность команд двух видов:

  1. Увеличить число на 1.
  2. Увеличить число в X раз.
Вася выбирает целое положительное число X и сообщает Пете. Петя в ответ выполняет задуманную последовательность команд, начиная с числа 1, и сообщает Васе получившееся число. Вася предлагает различные числа X до тех пор, пока не сумеет угадать последовательность команд, задуманную Петей. Если Вася правильно угадал последовательность, затратив не более 20 запросов, то он выигрывает. В противном случае выигрывает Петя.

Игра наскучила Пете, и он написал программу, которая играет за него. Программа действует почти так же, как Петя, однако если результат вычислений превосходит 2 × 109, программа сообщает число 1 вместо результата.

Теперь Вася хочет написать программу, которая выиграет у программы Пети.

Протокол взаимодействия

На каждом шаге взаимодействия, кроме последнего, ваша программа должна:

  1. Вывести целое число X в выходной поток.
  2. Ввести результат вычисления из входного потока.

На последнем шаге программа должна вывести строку, состоящую из символов + и *, обозначающих соответственно команды "Увеличить число на 1" и "Увеличить число в X раз".

После каждого шага, включая последний, следует вывести перевод строки и выполнить сброс буфера (flush).

Ограничения

Количество команд в последовательности находится в диапазоне от 1 до 20

1 ≤ X ≤ 2 × 109

Пример

Если Петя задумал последовательность +*++, а Вася предложил выполнить её для X = 3, то Петя ответит ему числом 8. Такое же число 8 получилось бы, если бы Петя задумал *+++++. Поэтому Вася пока не может однозначно угадать Петину последовательность, и должен сделать ещё один ход.


0.068s 0.009s 15