Problem: Petya wrote a programme on C++ that calculated a very interesting function f(n). Petya ran the program with a certain value of n and went to the kitchen to have some tea. The history has no records concerning how long the program had been working. By the time Petya returned, it had completed the calculations and had the result. However while Petya was drinking tea, a sly virus managed to destroy the input file so that Petya can't figure out for which value of n the program was run. Help Petya, carry out the inverse function!

Mostly, the program consists of a function in C++ with the following simplified syntax:

  * 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



The whitespaces in a operatorSequence are optional.

Thus, we have a function, in which body there are two kinds of operators. There is the operator "return arithmExpr;" that returns the value of the expression as the value of the function, and there is the conditional operator "if (logicalExpr) return arithmExpr;" that returns the value of the arithmetical expression when and only when the logical expression is true. Guaranteed that no other constructions of C++ language — cycles, assignment operators, nested conditional operators etc, and other variables except the n parameter are used in the function. All the constants are integers in the interval [0..32767].

The operators are performed sequentially. After the function has returned a value other operators in the sequence are not performed. Arithmetical expressions are performed taking into consideration the standard priority of the operations. It means that first all the products that are part of the sum are calculated. During the calculation of the products the operations of multiplying and division are performed from the left to the right. Then the summands are summed, and the addition and the subtraction are also performed from the left to the right. Operations ">" (more), "<" (less) and "==" (equals) also have standard meanings.

Now you've got to pay close attention! The program is compiled with the help of 15-bit Berland C++ compiler invented by a Berland company BerSoft, that's why arithmetical operations are performed in a non-standard way. Addition, subtraction and multiplication are performed modulo 32768 (if the result of subtraction is negative, then 32768 is added to it until the number belongs to the interval [0..32767]). Division "/" is a usual integer division where the remainder is omitted.

Examples of arithmetical operations: 

<image>

Guaranteed that for all values of n from 0 to 32767 the given function is performed correctly. That means that:

1. Division by 0 never occures.

2. When performing a function for the value n = N recursive calls of the function f may occur only for the parameter value of 0, 1, ..., N - 1. Consequently, the program never has an infinite recursion.

3. As the result of the sequence of the operators, the function always returns a value.

We have to mention that due to all the limitations the value returned by the function f is independent from either global variables or the order of performing the calculations of arithmetical expressions as part of the logical one, or from anything else except the value of n parameter. That's why the f function can be regarded as a function in its mathematical sense, i.e. as a unique correspondence between any value of n from the interval [0..32767] and a value of f(n) from the same interval.

Given the value of f(n), and you should find n. If the suitable n value is not unique, you should find the maximal one (from the interval [0..32767]).

Input

The first line has an integer f(n) from the interval [0..32767]. The next lines have the description of the function f. In the description can be found extra spaces and line breaks (see the examples) which, of course, can’t break key words int, if, return and numbers. The size of input data can’t exceed 100 bytes.

Output

Output a single number — the answer to the problem. If there’s no answer, output "-1" (without quotes).

Examples

Input

17
int f(int n)
{
if (n &lt; 100) return 17;
if (n &gt; 99) return 27;
}


Output

99


Input

13
int f(int n)
{
if (n == 0) return 0;
return f(n - 1) + 1;
}


Output

13

Input

144
int f(int n)
{
if (n == 0) return 0;
if (n == 1) return n;
return f(n - 1) + f(n - 2);
}

Output

24588

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 32768;
inline int _add(int a, int b) { return (a + b) % MOD; }
inline int _sub(int a, int b) { return (a - b + MOD) % MOD; }
inline int _mul(int a, int b) { return a * b % MOD; }
inline int _div(int a, int b) { return a / b; }
struct Func;
struct Node {
  enum Op {
    NUM,
    ADD,
    SUB,
    MUL,
    DIV,
    VAR,
    FUN,
  };
  Op op;
  int val;
  Node* lhs;
  Node* rhs;
  Node(Op op, int val = 0);
  Node(Op op, Node* lhs, Node* rhs = NULL);
  int eval(int var, const Func* fun) const;
};
struct Expr {
  Node* expr;
  Expr(string str);
  int eval(int var, const Func* fun) const;
};
struct Cond {
  enum Cmp {
    LT,
    EQ,
    GT,
  };
  Cmp cmp;
  Expr *lhs, *rhs;
  Cond(string str);
  bool eval(int var, const Func* fun) const;
};
struct Func {
  static map<int, int> tab;
  vector<pair<Cond*, Expr*> > stat;
  Func(string Func);
  int eval(int var) const;
};
map<int, int> Func::tab;
string trim(string s) {
  s.erase(0, s.find_first_not_of(' '));
  if (!s.empty()) {
    s.erase(s.find_last_not_of(' ') + 1);
  }
  return s;
}
string skip(string s, string t) {
  string::size_type pos = 0;
  for (string::iterator c = t.begin(); c != t.end(); ++c) {
    pos = s.find(*c, pos) + 1;
  }
  return s.substr(pos);
}
string::size_type paren(string s, string::size_type pos) {
  int c = 1;
  while (c > 0) {
    if (s[pos] == '(') {
      ++c;
    } else if (s[pos] == ')') {
      --c;
    }
    ++pos;
  }
  return pos;
}
Node::Node(Op op, int val) : op(op), val(val) {}
Node::Node(Op op, Node* lhs, Node* rhs) : op(op), lhs(lhs), rhs(rhs) {}
int Node::eval(int var, const Func* fun) const {
  switch (op) {
    case NUM:
      return val;
    case ADD:
      return _add(lhs->eval(var, fun), rhs->eval(var, fun));
    case SUB:
      return _sub(lhs->eval(var, fun), rhs->eval(var, fun));
    case MUL:
      return _mul(lhs->eval(var, fun), rhs->eval(var, fun));
    case DIV:
      return _div(lhs->eval(var, fun), rhs->eval(var, fun));
    case VAR:
      return var;
    case FUN:
      return fun->eval(lhs->eval(var, fun));
    default:
      throw 1;
  }
}
Expr::Expr(string str) {
  char* ptr;
  string::size_type pos;
  vector<Node::Op> op;
  vector<Node*> val;
  while (true) {
    str = trim(str);
    if (str[0] == 'n') {
      val.push_back(new Node(Node::VAR));
      str = str.substr(1);
    } else if (str[0] == 'f') {
      str = str.substr(str.find('(') + 1);
      pos = paren(str, 0);
      val.push_back(
          new Node(Node::FUN, (new Expr(str.substr(0, pos - 1)))->expr));
      str = str.substr(pos);
    } else {
      val.push_back(new Node(Node::NUM, strtol(str.c_str(), &ptr, 0)));
      str = str.substr(ptr - str.c_str());
    }
    str = trim(str);
    if (str.empty()) {
      while (!op.empty()) {
        Node* rhs = val.back();
        val.pop_back();
        Node* lhs = val.back();
        val.pop_back();
        val.push_back(new Node(op.back(), lhs, rhs));
        op.pop_back();
      }
      break;
    } else if (str[0] == '*' || str[0] == '/') {
      while (!op.empty() &&
             (op.back() == Node::MUL || op.back() == Node::DIV)) {
        Node* rhs = val.back();
        val.pop_back();
        Node* lhs = val.back();
        val.pop_back();
        val.push_back(new Node(op.back(), lhs, rhs));
        op.pop_back();
      }
      op.push_back(str[0] == '*' ? Node::MUL : Node::DIV);
    } else if (str[0] == '+' || str[0] == '-') {
      while (!op.empty()) {
        Node* rhs = val.back();
        val.pop_back();
        Node* lhs = val.back();
        val.pop_back();
        val.push_back(new Node(op.back(), lhs, rhs));
        op.pop_back();
      }
      op.push_back(str[0] == '+' ? Node::ADD : Node::SUB);
    }
    str = str.substr(1);
  }
  expr = val[0];
}
int Expr::eval(int var, const Func* fun) const { return expr->eval(var, fun); }
Cond::Cond(string str) {
  string::size_type pos;
  if ((pos = str.find("<")) != string::npos) {
    cmp = LT;
    lhs = new Expr(str.substr(0, pos));
    rhs = new Expr(str.substr(pos + 1));
  } else if ((pos = str.find(">")) != string::npos) {
    cmp = GT;
    lhs = new Expr(str.substr(0, pos));
    rhs = new Expr(str.substr(pos + 1));
  } else {
    pos = str.find("==");
    cmp = EQ;
    lhs = new Expr(str.substr(0, pos));
    rhs = new Expr(str.substr(pos + 2));
  }
}
bool Cond::eval(int var, const Func* fun) const {
  int l = lhs->eval(var, fun);
  int r = rhs->eval(var, fun);
  switch (cmp) {
    case LT:
      return l < r;
    case GT:
      return l > r;
    case EQ:
      return l == r;
    default:
      throw 2;
  }
}
Func::Func(string str) {
  string::size_type pos;
  string tmp;
  str = str.substr(str.find('{') + 1);
  str = str.substr(0, str.find('}'));
  str = trim(str);
  while ((pos = str.find(';')) != string::npos) {
    tmp = str.substr(0, pos);
    str = str.substr(pos + 1);
    tmp = trim(tmp);
    string cond;
    string expr;
    if (tmp.substr(0, 2) == "if") {
      pos = tmp.find('(');
      tmp = tmp.substr(pos + 1);
      pos = paren(tmp, 0);
      cond = tmp.substr(0, pos - 1);
      tmp = tmp.substr(pos);
    } else {
      cond = "0 == 0";
    }
    expr = skip(tmp, "return");
    stat.push_back(make_pair(new Cond(cond), new Expr(expr)));
  }
}
int Func::eval(int var) const {
  if (tab.count(var) != 0) {
    return tab[var];
  }
  int& ret = tab[var];
  for (vector<pair<Cond*, Expr*> >::const_iterator it = stat.begin();
       it != stat.end(); ++it) {
    if (it->first->eval(var, this)) {
      return ret = it->second->eval(var, this);
    }
  }
  throw 3;
}
int main() {
  int x, y;
  string code;
  char buf[4096];
  x = -1;
  scanf("%d", &y);
  while (scanf("%s", buf) != EOF) {
    code += buf;
    code += ' ';
  }
  Func f(code);
  try {
    for (int i = 0; i < MOD; ++i) {
      if (f.eval(i) == y) {
        x = i;
      }
    }
    printf("%d\n", x);
  } catch (int ex) {
    printf("ex = %d\n", ex);
    throw;
  }
  return 0;
}