## 1) Abridged problem statement

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

- `print <expression>`: evaluate the integer expression and output the value.
- `define <operand1> <operand2>`: create a **substitution rule**: every occurrence of `operand1` is replaced by `operand2`, recursively, until reaching an **undefined integer constant**.

Operands are either:
- a **non-negative integer constant**, or
- a **variable name** (case-insensitive, up to length 10; letters then letters/digits).

Rules/constraints:
- Redefining an already defined operand is **ignored**.
- Any definition that would create a **cycle** (circular dependency) is **ignored**.
- Any identifier used in an expression that does **not** ultimately resolve to an integer constant has value **0**.
- Expression operators: `+ - * / % ^`, parentheses, unary `+/-`.
  - Precedence: unary > `^` > `* / %` > `+ -`
  - Associativity: `^` is **right-associative**, others left-associative.
- Division/modulo are **special**:
  - Use absolute values for division/remainder, then apply the sign of the *true quotient* to the result.
- Guarantees: denominator never 0, exponent non-negative, no `0^0`.
- Limits: up to 30000 defines, 2000 prints.

---

## 2) Detailed editorial (how the solution works)

### Key idea: substitutions form a directed graph (like DSU/parent pointers)

Each `define A B` means: **A points to B** (A is replaced by B). Because:
- redefining A is ignored ⇒ each node has at most one outgoing edge
- cycles must be rejected

So we maintain a map `parent[A] = B`.

To apply substitutions recursively, we need to follow links:
`A -> parent[A] -> parent[parent[A]] -> ...`

This is exactly a **disjoint-set / union-find style “find”** operation with **path compression**:
- `find(x)` returns the final token reached (a token that has no parent mapping).
- While returning, compress pointers so future finds are fast.

Even though this is not classic DSU unioning sets, the “parent-pointer chain + path compression” still applies.

### Normalization

Variables are case-insensitive, constants are not (they’re digits anyway). So:
- If token starts with a digit: keep as-is
- Else lowercase it

### Preventing invalid defines

When reading `define a b`:
1. If `a` is already defined (`parent.count(a)`), ignore.
2. Otherwise, check if it would create a cycle:
   - Let `rb = find(b)` (ultimate representative of b).
   - If `rb == a`, then adding `a -> b` would make a cycle ⇒ ignore.
   - Else set `parent[a] = b`.

This matches the statement’s “circular dependence ignored” rule.

### Resolving a token in an expression

When evaluating expressions:
- Read token (number or identifier).
- Compute `r = find(normalize(token))`
- If `r` is a number (starts with digit): value is that integer.
- Else it never resolved to an integer constant ⇒ value is `0`.

That implements:
> “If some identifier is used … not yet defined to be substituted by some integer constant, its value is set to zero.”

### Expression parsing: recursive descent with precedence and associativity

We parse expressions using standard recursive descent:

- `expr := term (('+'|'-') term)*`
- `term := power (('*'|'/'|'%') power)*`
- `power := unary ('^' power)?`  (**right-associative** due to recursion on the right)
- `unary := ('+'|'-') unary | atom`
- `atom := NUMBER|IDENT | '(' expr ')'`

Spaces are skipped between tokens.

### Implementing `^` (power)

Exponent is non-negative. Base may be negative.
We compute integer power by fast exponentiation. For a negative base:
- result is negative iff exponent is odd.

The C++ uses `__int128` internally to avoid intermediate overflow (problem guarantees final results fit within limits described).

### Special division and modulo

Defined as:
- `div(a,b) = sign(a/b) * (|a| / |b|)` (integer division truncating toward 0 after abs)
- `mod(a,b)` similarly keeps `|a| % |b|` and applies the sign of the true quotient; if remainder is 0, return 0.

This matches sample behavior like `31 % -5 = -1`.

### Complexity

- Each `define` and each token resolution uses `find()` with path compression ⇒ effectively near O(1) amortized.
- Up to 2000 print lines, each expression length ≤ 200 characters ⇒ parsing is fast.
- Fits easily in limits.

---

## 3) Provided C++ solution with detailed line-by-line comments

```cpp
#include <bits/stdc++.h>              // Includes almost all standard C++ headers (common CP shortcut)
using namespace std;

// Helper stream operators (not essential to the solution, but included in template)
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {                 // Read each element of the vector
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {                  // Output each element separated by spaces
        out << x << ' ';
    }
    return out;
};

// Store all input lines (program lines)
vector<string> lines;

// Substitution mapping: parent[a] = b means "replace a with b"
map<string, string> parent;

// Normalize token for case-insensitive identifiers:
// - if empty or starts with digit => number: keep it
// - else => lower-case it
string normalize(const string& s) {
    if(s.empty() || isdigit(s[0])) {
        return s;
    }
    string r = s;
    for(char& c: r) {
        c = tolower(c);
    }
    return r;
}

// Follow substitution links with path compression.
// If s has no mapping, it is its own representative.
string find(const string& s) {
    auto it = parent.find(s);
    if(it == parent.end()) {
        return s;                     // Not defined => representative is itself
    }
    // Path compression: rewrite parent[s] directly to the final representative
    return it->second = find(it->second);
}

// Convert a token appearing in an expression into its numeric value:
// - apply normalization and substitutions
// - if final token is a number => return it
// - otherwise => undefined identifier (or unresolved chain) => 0
int64_t resolve_token(const string& token) {
    string r = find(normalize(token));
    if(!r.empty() && isdigit(r[0])) {
        return stoll(r);              // Convert numeric string to int64
    }
    return 0;                         // Not a numeric constant => treated as 0
}

// Integer exponentiation for non-negative exponent.
// Handles negative base: result negative iff exponent is odd.
int64_t power(int64_t base, int64_t exp) {
    bool neg = base < 0 && exp % 2 == 1; // Sign rule for negative base
    __int128 b = abs(base), result = 1;  // Use __int128 to reduce overflow risk in intermediates
    while(exp > 0) {
        if(exp & 1) {                    // If current bit set, multiply into result
            result *= b;
        }
        b *= b;                          // Square base each step
        exp >>= 1;                       // Next bit
    }
    return neg ? -(int64_t)result : (int64_t)result;
}

// Custom integer division per statement:
// quotient = sign(true quotient) * (|a| / |b|)
int64_t custom_div(int64_t a, int64_t b) {
    int64_t sign = ((a >= 0) == (b >= 0)) ? 1 : -1; // Same sign => positive, else negative
    return sign * (abs(a) / abs(b));                 // Integer division on absolute values
}

// Custom modulo per statement:
// remainder = sign(true quotient) * (|a| % |b|), but 0 stays 0.
int64_t custom_mod(int64_t a, int64_t b) {
    int64_t sign = ((a >= 0) == (b >= 0)) ? 1 : -1;  // Sign of quotient
    int64_t rem = abs(a) % abs(b);                   // Absolute remainder
    return rem == 0 ? 0 : sign * rem;                // Keep 0 as 0, else apply sign
}

// Recursive-descent parser for expressions with correct precedence/associativity
struct Parser {
    const string& s;   // expression string
    int pos;           // current parse position

    Parser(const string& str) : s(str), pos(0) {}

    // Skip spaces
    void skip() {
        while(pos < (int)s.size() && s[pos] == ' ') {
            pos++;
        }
    }

    // Read next token: either a number [0-9]+ or identifier [A-Za-z][A-Za-z0-9]*
    string read_token() {
        skip();
        if(pos >= (int)s.size()) {
            return "";
        }
        int start = pos;
        if(isdigit(s[pos])) {
            while(pos < (int)s.size() && isdigit(s[pos])) {
                pos++;
            }
        } else if(isalpha(s[pos])) {
            while(pos < (int)s.size() && isalnum(s[pos])) {
                pos++;
            }
        }
        return s.substr(start, pos - start);
    }

    // expr := term (('+'|'-') term)*
    int64_t parse_expr() {
        int64_t val = parse_term();
        while(true) {
            skip();
            if(pos < (int)s.size() && (s[pos] == '+' || s[pos] == '-')) {
                char op = s[pos++];     // consume operator
                int64_t r = parse_term();
                val = op == '+' ? val + r : val - r;
            } else {
                break;
            }
        }
        return val;
    }

    // term := power (('*'|'/'|'%') power)*
    int64_t parse_term() {
        int64_t val = parse_power();
        while(true) {
            skip();
            if(pos < (int)s.size() &&
               (s[pos] == '*' || s[pos] == '/' || s[pos] == '%')) {
                char op = s[pos++];     // consume operator
                int64_t r = parse_power();
                if(op == '*') {
                    val *= r;
                } else if(op == '/') {
                    val = custom_div(val, r);
                } else {
                    val = custom_mod(val, r);
                }
            } else {
                break;
            }
        }
        return val;
    }

    // power := unary ('^' power)?
    // Right-associative because we recurse on parse_power() on the right side.
    int64_t parse_power() {
        int64_t val = parse_unary();
        skip();
        if(pos < (int)s.size() && s[pos] == '^') {
            pos++;                      // consume '^'
            return power(val, parse_power());
        }
        return val;
    }

    // unary := ('+'|'-') unary | atom
    int64_t parse_unary() {
        skip();
        if(pos < (int)s.size() && s[pos] == '-') {
            pos++;                      // consume '-'
            return -parse_unary();
        }
        if(pos < (int)s.size() && s[pos] == '+') {
            pos++;                      // consume '+'
            return parse_unary();
        }
        return parse_atom();
    }

    // atom := '(' expr ')' | token
    int64_t parse_atom() {
        skip();
        if(pos < (int)s.size() && s[pos] == '(') {
            pos++;                      // consume '('
            int64_t val = parse_expr();
            skip();
            if(pos < (int)s.size() && s[pos] == ')') {
                pos++;                  // consume ')'
            }
            return val;
        }
        // token can be number or identifier; resolve via substitution rules
        return resolve_token(read_token());
    }
};

// Read entire input as lines (each line is one statement)
void read() {
    string line;
    while(getline(cin, line)) {
        lines.push_back(line);
    }
}

void solve() {
    // Iterate program lines and execute them in order.
    // "define" updates substitution mapping; "print" evaluates expression and prints result.

    for(auto& line: lines) {
        int i = 0;
        while(i < (int)line.size() && line[i] == ' ') { // skip leading spaces
            i++;
        }

        // Check command keyword at position i
        if(line.compare(i, 5, "print") == 0) {
            // Everything after "print" is the expression (possibly with spaces)
            string expr = line.substr(i + 5);
            Parser p(expr);
            cout << p.parse_expr() << "\n";
        } else if(line.compare(i, 6, "define") == 0) {
            // Parse "define op1 op2"
            string rest = line.substr(i + 6);
            istringstream iss(rest);
            string op1, op2;
            iss >> op1 >> op2;

            string a = normalize(op1), b = normalize(op2);

            // Ignore redefinition attempts
            if(!parent.count(a)) {
                // Detect cycle: if b ultimately resolves to a, then a->b would form a cycle
                string rb = find(b);
                if(rb != a) {
                    parent[a] = b;     // store substitution (note: stores raw b, not rb)
                }
            }
        }
    }
}

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

    int T = 1;                          // Single test case (entire input is one program)
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }
    return 0;
}
```

---

## 4) Python solution (equivalent) with 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 or 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 an expression:
    - apply normalize + recursive substitution (find)
    - if ends at a numeric constant => return it
    - else => treat as 0
    """
    r = find(normalize(tok))
    if r and r[0].isdigit():
        return int(r)
    return 0

def power(base: int, exp: int) -> int:
    """Fast exponentiation; exp is non-negative. Handle negative base sign."""
    neg = (base < 0 and (exp % 2 == 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 per statement: 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 per statement: sign(a/b) * (|a|%|b|), but 0 remainder stays 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 for PL/Cool expressions."""
    def __init__(self, s: str):
        self.s = s
        self.pos = 0

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

    def read_token(self) -> str:
        """Read a number or identifier token."""
        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
        return self.s[start:self.pos]

    def parse_expr(self) -> int:
        """expr := term (('+'|'-') term)*"""
        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
                r = self.parse_term()
                val = val + r if op == '+' else val - r
            else:
                break
        return val

    def parse_term(self) -> int:
        """term := power (('*'|'/'|'%') power)*"""
        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
                r = self.parse_power()
                if op == '*':
                    val *= r
                elif op == '/':
                    val = custom_div(val, r)
                else:
                    val = custom_mod(val, r)
            else:
                break
        return val

    def parse_power(self) -> int:
        """power := unary ('^' power)?  (right-associative)"""
        val = self.parse_unary()
        self.skip()
        if self.pos < len(self.s) and self.s[self.pos] == '^':
            self.pos += 1
            return power(val, self.parse_power())
        return val

    def parse_unary(self) -> int:
        """unary := ('+'|'-') unary | atom"""
        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()

    def parse_atom(self) -> int:
        """atom := '(' expr ')' | token"""
        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
        return resolve_token(self.read_token())

def main():
    lines = sys.stdin.read().splitlines()

    out = []
    for line in lines:
        # skip leading spaces
        i = 0
        while i < len(line) and line[i] == ' ':
            i += 1

        if line.startswith("print", i):
            expr = line[i + 5:]               # 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:
                op1, op2 = parts[0], parts[1]
                a = normalize(op1)
                b = normalize(op2)

                # Ignore redefinitions
                if a not in parent:
                    # Cycle check: if b ultimately becomes a, ignore
                    rb = find(b)
                    if rb != a:
                        parent[a] = b

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

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

---

## 5) Compressed editorial

Maintain substitutions from `define` as parent pointers `a -> b` with **path-compressed find()**. Normalize identifiers to lowercase (numbers unchanged). Reject `define` if `a` already defined or if `find(b) == a` (cycle). To evaluate an expression token, compute `r = find(token)`; if `r` is numeric return it, else return 0. Parse expressions via recursive descent with precedence: unary > `^` (right-assoc) > `* / %` > `+ -`. Implement `^` with fast exponentiation. Implement special `/` and `%` using absolute values then applying sign of true quotient. Output results for each `print`.