<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

215. PL/Cool
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The new IMB compiler "Unvisual Age for PL/Cool" is planned for release next month. Your task in this problem is to write the interpreter for the PL/Cool language so that the compiler programmers could test their product.

Program on PL/Cool can contain expressions. Each expression can contain integer constants and variables. The following operations are allowed: + (add), - (substract), * (multiply), / (divide), % (modulo), and ^ (raise). ll operations have their usual meaning and priority (^) > (*) = (/) = (%) > (+) = (-), all operations except ^ are evaluated from left to right, ^ is evaluated from right to left. Parenthesis can be used to change the order of evaluation, as usually. Unary minus and plus are allowed, their priority in this case is the highest.

Divide operation acts like integer division: first both operands are replaced with their absolute values, next integer division is performed, remainder is dropped, and finally the sign of the quotient is set equal to the sign of the true quotient of the operands. Taking modulo is perfomed the same way, except that the quotient is dropped and remainder is kept. For example, (80+4*75)/(56-2^2^3) = -1.

Program may contain variables. Variable name starts with a letter, which may be followed by letters and digits. Variable names are case insensitive. Maximal name length is 10 characters.

PL/Cool has two operators: "print" and "define". Program is the sequence of the operators, one on a line.

Operator "print" has the following syntax:

print <expression>


Here <expression> is any expression that may contain variables and integer constants. Operator "print" prints the value of the expression.

Operator "define" has the following syntax:

define <operand1> <operand2>


Here <operand1> and <operand2> are either variables or non-negative integer constants. After execution of the "define" operator, all occurences of the <operand1> are replaced with the <operand2>. Define operator can be used even to change the value of the integer constants, for example after

define 2 4

the value of 2+2 is 8.

Note that substitution is performed recursively, until some undefined constant is met, for example the following sequence of operators prints 8 and 10:

define 2 4
define 3 2
print 3+3
define 4 5
print 3+3


An attempt to redefine some variable or constant is ignored. An attempt to make a definition that leads to circular dependence is also ignored. For example, the following sequence prints 4 and 4, because the last two definitions are ignored.

define 2 4
define 3 2
define 2 5
print 3
define 4 2
print 3


If some identifier is used in the expression that is not yet defined to be substituted by some integer constant, its value is set to zero. For example, the following operator prints 3:

print x + 3


Input

Input file contains the program on PL/Cool. All numbers in the expressions, including numbers that occur during expression evaluation, do not exceed 109 by their absolute value. The total number of "define" operators does not exceed 30000, the total number of "print" operators does not exceed 2000, the length of each line does not exceed 200 characters.

In case of division denominator is never zero, zero is not raised to zero power and power exponent is always non-negative.

Output

Output file must contain the output of all print operators in the order they are executed, one on a line.

Sample test(s)

Input
print (80+4*75)/(56-2^ 2^ 3)
print 30/-1
print 31%-5
print 0^3
print 2+2
define 2 3
print 2+2
define 3 x
print 2+2
define x 2
print 2+2
define 2 5
print 2+2
define x 7
print 2+2

Output
-1
-30
-1
0
4
6
0
0
0
14
Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-30

<|response|>
## 1) Abridged problem statement (concise)

You must interpret a line-based language **PL/Cool** with two statements:

- `define A B` — create a substitution rule: every occurrence of operand `A` is replaced by operand `B` (recursively).
- `print <expression>` — evaluate an integer expression and output its value.

Operands `A`, `B`, and expression tokens are:
- **non-negative integer constants**, or
- **identifiers**: letter followed by letters/digits (case-insensitive, length ≤ 10).

Rules:
- Redefining an already defined operand is ignored.
- Any definition that would create a substitution cycle is ignored.
- During expression evaluation, a token is substituted repeatedly until it becomes an **undefined token**.  
  If that final token is a number → use it; otherwise (identifier) → value is **0**.

Expression operators: `+ - * / % ^`, parentheses, unary `+/-`.  
Precedence: unary > `^` > `* / %` > `+ -`  
Associativity: `^` is right-to-left; others left-to-right.

Special integer `/` and `%`:
- Compute using `abs()` operands, then apply the sign of the true quotient to the result.

Constraints: up to 30000 `define`, 2000 `print`, each line ≤ 200 chars.

---

## 2) Key observations

1. **Defines form a functional directed graph**  
   Each left operand `A` can be defined at most once, so every node has **≤ 1 outgoing edge**: `A → B`.

2. **Resolving substitutions is “follow parent pointers”**  
   To evaluate a token, we repeatedly follow `A → parent[A] → parent[parent[A]] → ...` until there’s no rule.

3. **Path compression makes resolution fast**  
   This is the same idea as DSU `find()`: once we know the final target, we rewrite intermediate pointers to jump there next time.

4. **Cycle detection is easy**  
   For `define A B`, if `find(B) == A`, then adding `A → B` creates a cycle → ignore.

5. **Parsing expressions needs correct precedence + associativity**  
   A standard recursive-descent parser handles this cleanly, especially `^` being right-associative:
   - parse `power := unary ('^' power)?`

6. **Undefined identifiers become 0**  
   After substitution, if the final token is not a number, treat its value as 0.

---

## 3) Full solution approach

### A) Maintain substitution rules with parent pointers
- Use a map/dictionary: `parent[token] = token2`
- Normalize tokens:
  - If token is an identifier → lowercase it (case-insensitive)
  - Numbers stay as-is.

### B) `find(token)` with path compression
`find(x)` returns the final token reached by following `parent` links until undefined.
- If `x` not in `parent`, return `x`.
- Else return `find(parent[x])` and compress `parent[x]` to that result.

### C) Process `define A B`
1. Normalize `A`, `B`.
2. If `A` already has a parent → ignore (redefinition).
3. Compute `rb = find(B)`.
4. If `rb == A` → would create a cycle → ignore.
5. Otherwise store `parent[A] = B`.

### D) Resolve a token in expressions
To evaluate a token `t`:
1. `r = find(normalize(t))`
2. If `r` is a numeric string → value = that integer
3. Else → value = 0

### E) Parse and evaluate expressions (recursive descent)
Grammar (with precedence):
- `expr   := term (('+'|'-') term)*`
- `term   := power (('*'|'/'|'%') power)*`
- `power  := unary ('^' power)?`  (right associative)
- `unary  := ('+'|'-') unary | atom`
- `atom   := NUMBER | IDENT | '(' expr ')'`

Implement operations:
- `^`: fast exponentiation, exponent non-negative.
- `/` and `%`: custom rules:
  - `div(a,b) = sign(a/b) * (|a| // |b|)`
  - `mod(a,b) = sign(a/b) * (|a| % |b|)` but if remainder is 0, return 0.

### F) Execute input line-by-line
- If line starts with `print`: parse expression substring and output value.
- If line starts with `define`: parse two operands and update rules (if allowed).

Complexity: almost linear in total input size; `find()` is near O(1) amortized.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  PL/Cool interpreter:
  - Substitutions are stored as parent pointers: parent[a] = b.
  - find(x) follows pointers with path compression.
  - Expressions are evaluated by recursive-descent parsing with correct precedence:
      unary > ^ (right-assoc) > * / % > + -
  - Undefined identifiers evaluate to 0.
*/

static map<string, string> parentPtr; // substitution mapping

// Lowercase identifiers (case-insensitive). Numbers are left unchanged.
static string normalizeToken(const string& s) {
    if (s.empty()) return s;
    if (isdigit((unsigned char)s[0])) return s; // number
    string t = s;
    for (char &c : t) c = (char)tolower((unsigned char)c);
    return t;
}

// Find final representative with path compression.
static string findRep(const string& s) {
    auto it = parentPtr.find(s);
    if (it == parentPtr.end()) return s;            // no substitution defined
    return it->second = findRep(it->second);        // compress path
}

// Resolve token to integer: follow substitutions; if ends as number => parse; else 0.
static long long resolveValue(const string& token) {
    string r = findRep(normalizeToken(token));
    if (!r.empty() && isdigit((unsigned char)r[0])) return stoll(r);
    return 0;
}

// Fast exponentiation, exp >= 0. Uses __int128 for safer intermediate multiplication.
static long long ipow(long long base, long long exp) {
    bool neg = (base < 0 && (exp & 1LL)); // negative result iff base neg and exp odd
    __int128 b = llabs(base);
    __int128 res = 1;
    while (exp > 0) {
        if (exp & 1LL) res *= b;
        b *= b;
        exp >>= 1LL;
    }
    long long ans = (long long)res;
    return neg ? -ans : ans;
}

// Custom division described in statement.
static long long customDiv(long long a, long long b) {
    long long sign = ((a >= 0) == (b >= 0)) ? 1 : -1;
    return sign * (llabs(a) / llabs(b));
}

// Custom modulo described in statement.
static long long customMod(long long a, long long b) {
    long long sign = ((a >= 0) == (b >= 0)) ? 1 : -1;
    long long rem = llabs(a) % llabs(b);
    if (rem == 0) return 0;
    return sign * rem;
}

// Recursive-descent parser for a single expression string.
struct Parser {
    const string &s;
    int pos = 0;

    Parser(const string& str) : s(str) {}

    void skipSpaces() {
        while (pos < (int)s.size() && s[pos] == ' ') pos++;
    }

    // Read NUMBER or IDENT token (without handling operators/parens).
    string readToken() {
        skipSpaces();
        if (pos >= (int)s.size()) return "";
        int start = pos;

        if (isdigit((unsigned char)s[pos])) {
            while (pos < (int)s.size() && isdigit((unsigned char)s[pos])) pos++;
        } else if (isalpha((unsigned char)s[pos])) {
            while (pos < (int)s.size() && isalnum((unsigned char)s[pos])) pos++;
        } else {
            // Not a token start (operator/parens/etc). Return empty.
            return "";
        }
        return s.substr(start, pos - start);
    }

    // expr := term (('+'|'-') term)*
    long long parseExpr() {
        long long val = parseTerm();
        while (true) {
            skipSpaces();
            if (pos < (int)s.size() && (s[pos] == '+' || s[pos] == '-')) {
                char op = s[pos++];
                long long rhs = parseTerm();
                if (op == '+') val += rhs;
                else val -= rhs;
            } else break;
        }
        return val;
    }

    // term := power (('*'|'/'|'%') power)*
    long long parseTerm() {
        long long val = parsePower();
        while (true) {
            skipSpaces();
            if (pos < (int)s.size() && (s[pos] == '*' || s[pos] == '/' || s[pos] == '%')) {
                char op = s[pos++];
                long long rhs = parsePower();
                if (op == '*') val *= rhs;
                else if (op == '/') val = customDiv(val, rhs);
                else val = customMod(val, rhs);
            } else break;
        }
        return val;
    }

    // power := unary ('^' power)?
    // Right-associative: parse RHS as another power().
    long long parsePower() {
        long long val = parseUnary();
        skipSpaces();
        if (pos < (int)s.size() && s[pos] == '^') {
            pos++;
            long long e = parsePower();
            return ipow(val, e);
        }
        return val;
    }

    // unary := ('+'|'-') unary | atom
    long long parseUnary() {
        skipSpaces();
        if (pos < (int)s.size() && s[pos] == '+') {
            pos++;
            return parseUnary();
        }
        if (pos < (int)s.size() && s[pos] == '-') {
            pos++;
            return -parseUnary();
        }
        return parseAtom();
    }

    // atom := '(' expr ')' | token
    long long parseAtom() {
        skipSpaces();
        if (pos < (int)s.size() && s[pos] == '(') {
            pos++;
            long long val = parseExpr();
            skipSpaces();
            if (pos < (int)s.size() && s[pos] == ')') pos++; // consume ')'
            return val;
        }
        string tok = readToken();
        return resolveValue(tok);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;
    while (getline(cin, line)) {
        // skip leading spaces
        int i = 0;
        while (i < (int)line.size() && line[i] == ' ') i++;

        if (line.compare(i, 5, "print") == 0) {
            string expr = line.substr(i + 5); // remainder after "print"
            Parser p(expr);
            cout << p.parseExpr() << "\n";
        } else if (line.compare(i, 6, "define") == 0) {
            // parse: define op1 op2 (operands have no spaces inside)
            string rest = line.substr(i + 6);
            istringstream iss(rest);
            string op1, op2;
            iss >> op1 >> op2;

            string a = normalizeToken(op1);
            string b = normalizeToken(op2);

            // Ignore redefinitions
            if (!parentPtr.count(a)) {
                // Cycle check: if b ultimately becomes a, then a->b creates a loop
                string rb = findRep(b);
                if (rb != a) {
                    parentPtr[a] = b;
                }
            }
        }
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

# parent[a] = b means "replace a with b"
parent = {}

def normalize(tok: str) -> str:
    """Lowercase identifiers (case-insensitive). Keep numbers unchanged."""
    if not tok:
        return tok
    if tok[0].isdigit():
        return tok
    return tok.lower()

def find(tok: str) -> str:
    """Follow substitution links with path compression."""
    if tok not in parent:
        return tok
    parent[tok] = find(parent[tok])
    return parent[tok]

def resolve_token(tok: str) -> int:
    """
    Resolve a token used in expressions:
    - normalize + follow substitutions
    - if ends at a number => int(value)
    - else => 0
    """
    r = find(normalize(tok))
    return int(r) if r and r[0].isdigit() else 0

def ipow(base: int, exp: int) -> int:
    """Fast exponentiation for exp >= 0. Handles negative base sign."""
    neg = (base < 0 and (exp & 1) == 1)
    b = abs(base)
    res = 1
    e = exp
    while e > 0:
        if e & 1:
            res *= b
        b *= b
        e >>= 1
    return -res if neg else res

def custom_div(a: int, b: int) -> int:
    """Division: sign(a/b) * (|a|//|b|)."""
    sign = 1 if (a >= 0) == (b >= 0) else -1
    return sign * (abs(a) // abs(b))

def custom_mod(a: int, b: int) -> int:
    """Modulo: sign(a/b) * (|a|%|b|), but keep 0 as 0."""
    sign = 1 if (a >= 0) == (b >= 0) else -1
    rem = abs(a) % abs(b)
    return 0 if rem == 0 else sign * rem

class Parser:
    """Recursive descent parser with PL/Cool operator precedence."""
    def __init__(self, s: str):
        self.s = s
        self.pos = 0

    def skip(self):
        while self.pos < len(self.s) and self.s[self.pos] == ' ':
            self.pos += 1

    def read_token(self) -> str:
        """Read NUMBER or IDENT starting at current position."""
        self.skip()
        if self.pos >= len(self.s):
            return ""
        start = self.pos
        c = self.s[self.pos]
        if c.isdigit():
            while self.pos < len(self.s) and self.s[self.pos].isdigit():
                self.pos += 1
        elif c.isalpha():
            while self.pos < len(self.s) and self.s[self.pos].isalnum():
                self.pos += 1
        else:
            return ""
        return self.s[start:self.pos]

    # expr := term (('+'|'-') term)*
    def parse_expr(self) -> int:
        val = self.parse_term()
        while True:
            self.skip()
            if self.pos < len(self.s) and self.s[self.pos] in "+-":
                op = self.s[self.pos]
                self.pos += 1
                rhs = self.parse_term()
                val = val + rhs if op == '+' else val - rhs
            else:
                break
        return val

    # term := power (('*'|'/'|'%') power)*
    def parse_term(self) -> int:
        val = self.parse_power()
        while True:
            self.skip()
            if self.pos < len(self.s) and self.s[self.pos] in "*/%":
                op = self.s[self.pos]
                self.pos += 1
                rhs = self.parse_power()
                if op == '*':
                    val *= rhs
                elif op == '/':
                    val = custom_div(val, rhs)
                else:
                    val = custom_mod(val, rhs)
            else:
                break
        return val

    # power := unary ('^' power)?
    # Right-associative by recursing on parse_power() on the RHS.
    def parse_power(self) -> int:
        val = self.parse_unary()
        self.skip()
        if self.pos < len(self.s) and self.s[self.pos] == '^':
            self.pos += 1
            exp = self.parse_power()
            return ipow(val, exp)
        return val

    # unary := ('+'|'-') unary | atom
    def parse_unary(self) -> int:
        self.skip()
        if self.pos < len(self.s) and self.s[self.pos] == '+':
            self.pos += 1
            return self.parse_unary()
        if self.pos < len(self.s) and self.s[self.pos] == '-':
            self.pos += 1
            return -self.parse_unary()
        return self.parse_atom()

    # atom := '(' expr ')' | token
    def parse_atom(self) -> int:
        self.skip()
        if self.pos < len(self.s) and self.s[self.pos] == '(':
            self.pos += 1
            val = self.parse_expr()
            self.skip()
            if self.pos < len(self.s) and self.s[self.pos] == ')':
                self.pos += 1
            return val
        tok = self.read_token()
        return resolve_token(tok)

def main():
    out = []
    for line in sys.stdin.read().splitlines():
        i = 0
        while i < len(line) and line[i] == ' ':
            i += 1

        if line.startswith("print", i):
            expr = line[i + 5:]  # substring after keyword
            p = Parser(expr)
            out.append(str(p.parse_expr()))

        elif line.startswith("define", i):
            rest = line[i + 6:]
            parts = rest.split()
            if len(parts) >= 2:
                a = normalize(parts[0])
                b = normalize(parts[1])

                # Ignore redefinition
                if a not in parent:
                    # Ignore if it makes a cycle
                    if find(b) != a:
                        parent[a] = b

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()
```

If you want, I can also add a short section of “gotchas” (like why `^` must be right-associative and why cycle check uses `find(b) == a`).