G. Обратная функция
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
64 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Петя написал программу на C++, вычисляющую значение одной интересной функции f(n). Петя запустил программу при некотором значении n и отправился на кухню пить чай. О том, сколько времени работала программа, история умалчивает. Когда Петя вернулся, она уже закончила выполнение и выдала результат. Однако пока Петя пил чай, коварный вирус успел уничтожить входной файл, поэтому Петя не может восстановить, для какого значения n была запущена программа. Помогите Пете: реализуйте обратную функцию!

Основную часть программы представляет собой функция на C++ со следующим упрощенным синтаксисом:

  • function ::= int f(int n) {operatorSequence}
  • operatorSequence ::= operator | operator operatorSequence
  • operator ::= return arithmExpr; | if (logicalExpr) return arithmExpr;
  • logicalExpr ::= arithmExpr > arithmExpr | arithmExpr < arithmExpr | arithmExpr == arithmExpr
  • arithmExpr ::= sum
  • sum ::= product | sum + product | sum - product
  • product ::= multiplier | product * multiplier | product / multiplier
  • multiplier ::= n | number | f(arithmExpr)
  • number ::= 0|1|2|... |32767

Пробелы и переводы строк в operatorSequence — необязательны.

Таким образом, имеется функция, в теле которой встречается два вида операторов. Это оператор "return arithmExpr;", возвращающий в качестве значения функции значение арифметического выражения, и условный оператор "if (logicalExpr) return arithmExpr;", который возвращает значение арифметического выражения в том и только в том случае, когда выполняется логическое выражение. Гарантируется, что никакие другие конструкции языка C++: циклы, операторы присваивания, вложенные условные операторы и т.д. и другие переменные, кроме параметра n, в функции не используются. Все константы являются целыми числами из промежутка [0..32767].

Операторы выполняются последовательно. После того, как произойдет возврат функцией некоторого значения, остальные операторы в последовательности не выполняются. Арифметические выражения вычисляются с учетом стандартного приоритета операций. Это означает, что сначала вычисляются все произведения, входящие в сумму. При вычислении произведения операции умножения и деления выполняются слева направо. Затем происходит суммирование слагаемых, при этом сложение и вычитание тоже выполняются слева направо. Операции ">" (больше), "<" (меньше) и "==" (равно) тоже имеют стандартный смысл.

Теперь внимание! Программа компилируется с помощью разработанного берляндской компанией BerSoft 15-битного компилятора Berland C++, поэтому арифметические действия выполняются нестандартным образом. Сложение, вычитание и умножение выполняются по модулю 32768 (если при вычитании получается отрицательное число, то к нему прибавляется 32768 до тех пор, пока оно не окажется в промежутке [0..32767]). Деление "/" — это обычное целочисленное деление с отбрасыванием остатка.

Примеры арифметических действий:

Гарантируется, что при любом значении n от 0 до 32767 заданная функция выполняется корректно. Это означает, что:

1. Не происходит деления на 0.

2. При выполнении функции для значения n = N рекурсивные вызовы функции f могут роисходить только для значений параметра 0, 1, ..., N - 1. Следовательно, программа никогда не уходит в бесконечную рекурсию.

3. В итоге выполнения последовательности операторов обязательно происходит возврат значения функции.

Заметим, что в силу всех введенных ограничений значение, возвращаемое функцией f, не зависит ни от глобальных переменных, ни от порядка вычисления арифметических выражений в составе логического, ни от чего либо другого, кроме значения параметра n. Поэтому функцию f можно рассматривать как функцию в математическом смысле, т.е. как однозначное соответствие каждому значению n из промежутка [0..32767] значения f(n) из того же промежутка.

Вам дано значение f(n), нужно найти n. Если подходящих значений n несколько, требуется определить максимальное (из промежутка [0..32767]).

Входные данные

В первой строке содержится целое число f(n) из промежутка [0..32767]. В следующих строках содержится описание функции f. В описании могут встречаться дополнительные пробелы и переводы строки (см. примеры), которые, разумеется, не могут разрывать ключевые слова int, if, return и числа. Размер входных данных не превосходит 100 байт.

Выходные данные

Выведите единственное число — ответ на задачу. Если решения не существует, выведите "-1" (без кавычек).

Примеры
Входные данные
17
int f(int n)
{
if (n < 100) return 17;
if (n > 99) return 27;
}
Выходные данные
99
Входные данные
13
int f(int n)
{
if (n == 0) return 0;
return f(n - 1) + 1;
}
Выходные данные
13
Входные данные
144
int f(int n)
{
if (n == 0) return 0;
if (n == 1) return n;
return f(n - 1) + f(n - 2);
}
Выходные данные
24588