<|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.

189. Perl-like Substr
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



A small Russian offshore company H&H decided to strike the world community and develop their own analogue (faster and with lots of features) of a well-known scripting language Perl. You are hired to participate in this project and your task is very simple - to code the function substr.
Function substr writes and reads separate substrings:
value = substr(string, offset, count);
value = substr(string, offset);
substr(string, offset, count) = newstring;
substr(string, offset) = newstring;
string(symbol in Perl marks a scalar variable, the strings in Perl are scalar variables) contains the initial string. offsetdefinesthebeginningofthesubstring.Positivevaluesofoffset are counted out from the beginning of the string, negative - from the end. If the offsetequalstozero, thesubstringbeginsfromthefirstsymbolofstring.Thethirdargumentcount defines the length of the substring. If countisomitted, substrreturnseverythingtotheendofthestring.Ifcount is negative, substr leaves that many characters off the end of the string.
Function substr can be used not only to get the substring from the string, but also to replace the substring with the new string. In the last case the lengths of the old substring and the new one can be different.
You are given a simple Perl-like program (refer to the input and output specifications) and your task is to output the result of its execution.

Input
The first line contains two natural numbers N (1<=N<=20) - the number of initialization lines in the program and M (1<=M<=300) - the number of remaining lines in the program. Next N lines (no one more than 10000 symbols) contain the string initialization in the following form:
name = "value";
name is the name of the string variable (always starts with symbol ).Thenameofthevariableconsistsofupto20(includingsymbol) alfa-numerical letters (and the inthebeginning).Thenameofthevariableisfollowedbysymbol" = ", andthenfollowsthevalueofthevariable - asequenceofalfa - numericalsymbolsandthepunctuators(space, comma, dot, hyphen, underline, colon, exclamationandquestionmarks)enclosedindoublequotes.Thelengthofthevalueisnotmorethan255symbols.Thenameofthevariable, symbol" = ", andthevaluecanbedelimitedbyoneormorespaces.Thereisalwaysasemicolonattheendoftheline.
EachofthefollowingMlinescontainsthelineoftheprograminoneofthefollowing6types: 
1. print(name); Output the value of variable name
2. print(substr(name, o[, c])); Output the substring from variable name
3. name1 = name2; Assignthevalueofvariablename1 to the value of variable name2
4. name1 = substr(name2, o[, c]); Assignthevalueofvariablename1 to the substring from variable name2
5. substr(name1, o[, c]) = name2; Replacethesubstringinname1with the value of name2
6. substr(name1, o[, c]) = substr(name2, o[, c]); Replacethesubstringinname1 with the substring from name2

Thesquarebracketsindicatethatthethirdargumentinsubstrcanbeomitted.Theremaybenospacesinsidethenamesofthevariablesandthenamesoffunctions, buttheremaybeoneorseveralspacesinallotherplaces.Thereissymbol";"attheendofeachline, thelengthofeachlineisnotmorethan255symbols.Thevaluesofthevariableswhichweren'tinitializedinthefirstNlinesoftheinputfileareconsideredasemptystrings"".Thetotalnumberofdifferentvariablesintheprogramisnotmorethan100.Novariablevaluewillhavethelengthofmorethan1000symbolsinthecourseoftheprogramexecution.
Theparametersc and ohavebeenchosenso, thatthesubstrreturnsthe"correct"substring, i.e.thebeginningandtheendofthesubstringarewithintheinitialstring, andthebeginningproceedstheend(substringisnotempty).
Youmustassumethatnamesofvariablesarecasesensitive.

Output
Theoutputfilemustcontaintheresultoftheprogramexecution - onelineforeachprint()operator.Noadditionalsymbols, spacesorlinebrakesintheoutputfilearepermitted.
Sampletest(s)
Input
29

a = "0123456789";

b = "abcdefghigklmn";
print(a);

print( substr(b, 1, 2));
substr(b, 0, 1) = substr(a, 2, 7);
c = b;
print(substr(c,0));

print(substr(a,  - 2,  - 1));
print(substr(a, -6, 2));

print(substr(a,  - 5));
print(substr(a, 1, 2));

Output
0123456789

bc

2345678bcdefghigklmn

8

45

56789

12
  
  
Author:	Ilya V. Elterman
Resource:	ACM International Collegiate Programming Contest 2003-2004

North-Eastern European Region, Southern Subregion
Date:	2003 October, 9

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

You are given a Perl-like program that manipulates **string variables** (names like `$a`) and supports:

- `print(name);`
- `print(substr(name, offset[, count]));`
- Assignments: `name1 = name2;` and `name1 = substr(name2, offset[, count]);`
- Replacement: `substr(name1, offset[, count]) = name2;` and `= substr(name2, offset[, count]);`

`substr(s, offset[, count])` uses Perl-like rules:

- `offset >= 0`: start at index `offset` (0-based from start)
- `offset < 0`: start at `len(s) + offset` (from end)
- If `count` omitted: take to end
- If `count >= 0`: length is `count`
- If `count < 0`: end at `len(s) + count` (leave `-count` chars off the end)

All offsets/counts are guaranteed to describe a **valid non-empty** substring.  
Uninitialized variables are empty strings.  
Simulate the program and output each `print` result on its own line.

---

## 2) Key observations

1. This is a **straight simulation** problem: maintain a map `variable -> current string`.
2. Only **6 statement forms** exist, so parsing can be simplified.
3. For program lines (not initialization), string literals never appear; therefore:
   - removing spaces from a line makes it easy to classify and parse (`print(...)`, `substr(...)=...`, `name=...`).
4. Correctness hinges on implementing `substr` exactly:
   - convert `offset` to a valid `start`
   - compute `end` depending on presence/sign of `count`
5. Substring replacement can be done by:
   - `s = s[0:start] + newValue + s[end:len]`

Constraints are small (≤ 300 lines, strings ≤ 1000), so O(length) per operation is fine.

---

## 3) Full solution approach

### Data structure
Use a dictionary/map:
- `vars[name]` = current string value  
If a variable is missing, treat as `""`.

### Input handling
The statement allows blank lines. A convenient strategy:
1. Read `N` and `M`.
2. Read the rest of the file line-by-line, ignore whitespace-only lines.
3. First `N` kept lines are initialization, next `M` are program lines.

### Parse initialization lines
Format: `name = "value";` with optional spaces.
- Extract variable name (starts with `$`, then alnum/underscore).
- Extract text between the first and last `"` and store it.

### Normalize program lines
Remove all regular spaces `' '` from the line (initializations already handled, and program lines contain no quoted strings).  
Then each line fits one of these top-level patterns:

1. `print(...)`
2. `substr(...)=...`  (replacement)
3. `name=...`         (assignment)

### Helper: parse `substr(...)` arguments
Inside `substr(...)` after normalization you get:
- `name,offset` or `name,offset,count`

Parse by splitting on commas.

### Helper: evaluate substring
Given `s`, `offset`, and optional `count`:
- `start = offset` if `offset >= 0` else `len(s) + offset`
- If no `count`: `end = len(s)`
- Else if `count >= 0`: `end = start + count`
- Else (`count < 0`): `end = len(s) + count`
Return `s[start:end]`.

### Execute statements
- **Print**
  - If argument starts with `substr(`: print evaluated substring
  - Else: print variable value
- **Assignment `name=rhs;`**
  - If `rhs` starts with `substr(`: evaluate substring and assign
  - Else: assign `vars[rhs]`
- **Replacement `substr(lhs...)=rhs;`**
  - Parse lhs substring spec → compute `[start,end)` in `vars[lhsName]`
  - Evaluate rhs to a string (variable or substring)
  - Replace slice

---

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

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

/*
  We simulate a small Perl-like language with:
  - string variables like $a
  - substr extraction and replacement
  - print

  Program lines contain no quoted literals, so we can safely remove spaces
  to simplify parsing.
*/

struct SubArgs {
    string name;
    int offset;
    int count;
    bool has_count;
};

// Remove only ' ' spaces (not tabs). This matches many accepted solutions and
// is enough for typical ICPC inputs. (You may extend to all whitespace if desired.)
static string strip_spaces(const string& s) {
    string t;
    t.reserve(s.size());
    for (char c : s) if (c != ' ') t.push_back(c);
    return t;
}

// Parse "name,offset" or "name,offset,count" from inside substr(...)
static SubArgs parse_substr_args(const string& inner) {
    int c1 = (int)inner.find(',');
    string name = inner.substr(0, c1);
    string rest = inner.substr(c1 + 1);

    int c2 = (int)rest.find(',');
    if (c2 == (int)string::npos) {
        return {name, stoi(rest), 0, false};
    }
    int offset = stoi(rest.substr(0, c2));
    int count  = stoi(rest.substr(c2 + 1));
    return {name, offset, count, true};
}

// Perl-like substr extraction according to the statement.
static string get_substr(const string& s, int offset, int count, bool has_count) {
    int n = (int)s.size();
    int start = (offset >= 0) ? offset : (n + offset);

    int end;
    if (!has_count) {
        end = n;                 // take to end
    } else if (count >= 0) {
        end = start + count;     // fixed length
    } else {
        end = n + count;         // leave -count chars off the end
    }

    return s.substr(start, end - start);
}

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

    int N, M;
    cin >> N >> M;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    // Read all remaining lines, ignoring blank/whitespace-only lines.
    vector<string> all;
    string line;
    while (getline(cin, line)) {
        bool blank = true;
        for (char c : line) {
            if (c != ' ' && c != '\t' && c != '\r') { blank = false; break; }
        }
        if (!blank) all.push_back(line);
    }

    vector<string> init_lines(all.begin(), all.begin() + N);
    vector<string> prog_lines(all.begin() + N, all.begin() + N + M);

    // Variable table. Accessing vars[name] creates "" automatically if missing.
    map<string, string> vars;

    // --- Parse initializations: $name = "value";
    for (const string& init : init_lines) {
        // Find variable name starting at '$'
        int pos = (int)init.find('$');
        int i = pos;
        string name;
        while (i < (int)init.size()) {
            char c = init[i];
            if (isalnum((unsigned char)c) || c == '$' || c == '_') {
                name.push_back(c);
                i++;
            } else break;
        }

        // Value is between first and last double quote
        int q1 = (int)init.find('"');
        int q2 = (int)init.rfind('"');
        vars[name] = init.substr(q1 + 1, q2 - q1 - 1);
    }

    // --- Execute program
    for (const string& raw : prog_lines) {
        string s = strip_spaces(raw);
        if (s.empty() || s == ";") continue;

        // 1) print(...)
        if (s.rfind("print(", 0) == 0) {
            // content between "print(" and ");"
            string inside = s.substr(6, s.size() - 8);

            // print(substr(...))
            if (inside.rfind("substr(", 0) == 0) {
                string inner = inside.substr(7, inside.size() - 8);
                SubArgs a = parse_substr_args(inner);
                cout << get_substr(vars[a.name], a.offset, a.count, a.has_count) << "\n";
            } else {
                // print(variable)
                cout << vars[inside] << "\n";
            }
        }
        // 2) replacement: substr(...)=...
        else if (s.rfind("substr(", 0) == 0) {
            int close = (int)s.find(')');
            string lhs_inner = s.substr(7, close - 7);             // inside lhs substr(...)
            string rhs = s.substr(close + 2, s.size() - close - 3); // after ")=" up to ';'

            SubArgs L = parse_substr_args(lhs_inner);

            // Evaluate RHS to a string
            string new_value;
            if (rhs.rfind("substr(", 0) == 0) {
                string rhs_inner = rhs.substr(7, rhs.size() - 8);
                SubArgs R = parse_substr_args(rhs_inner);
                new_value = get_substr(vars[R.name], R.offset, R.count, R.has_count);
            } else {
                new_value = vars[rhs];
            }

            // Replace the substring in vars[L.name]
            string& base = vars[L.name];
            int n = (int)base.size();
            int start = (L.offset >= 0) ? L.offset : (n + L.offset);

            int end;
            if (!L.has_count) end = n;
            else if (L.count >= 0) end = start + L.count;
            else end = n + L.count;

            base = base.substr(0, start) + new_value + base.substr(end);
        }
        // 3) assignment: name=...
        else {
            int eq = (int)s.find('=');
            string lhs = s.substr(0, eq);
            string rhs = s.substr(eq + 1, s.size() - eq - 2); // strip trailing ';'

            if (rhs.rfind("substr(", 0) == 0) {
                string rhs_inner = rhs.substr(7, rhs.size() - 8);
                SubArgs a = parse_substr_args(rhs_inner);
                vars[lhs] = get_substr(vars[a.name], a.offset, a.count, a.has_count);
            } else {
                vars[lhs] = vars[rhs];
            }
        }
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def strip_spaces(s: str) -> str:
    # Program lines contain no quoted strings, so removing spaces is safe.
    # (Initialization lines are parsed separately.)
    return s.replace(" ", "")

def parse_substr_args(inner: str):
    """
    Parse inside substr(...): "name,offset" or "name,offset,count"
    Assumes spaces already removed.
    """
    c1 = inner.find(",")
    name = inner[:c1]
    rest = inner[c1 + 1:]

    c2 = rest.find(",")
    if c2 == -1:
        return name, int(rest), 0, False
    offset = int(rest[:c2])
    count = int(rest[c2 + 1:])
    return name, offset, count, True

def get_substr(s: str, offset: int, count: int, has_count: bool) -> str:
    """
    Perl-like substr extraction based on the statement.
    """
    n = len(s)
    start = offset if offset >= 0 else n + offset

    if not has_count:
        end = n
    elif count >= 0:
        end = start + count
    else:
        end = n + count   # leave -count chars off the end

    return s[start:end]

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return

    # Read N M
    n, m = map(int, data[0].split())

    # Collect non-blank lines after the first line
    all_lines = []
    for line in data[1:]:
        if any(c not in " \t\r" for c in line):
            all_lines.append(line)

    init_lines = all_lines[:n]
    prog_lines = all_lines[n:n + m]

    # Variable table; missing variables are treated as ""
    vars = {}

    # Parse initializations: $name = "value";
    for line in init_lines:
        d = line.find("$")
        i = d
        name_chars = []
        while i < len(line) and (line[i].isalnum() or line[i] in "$_"):
            name_chars.append(line[i])
            i += 1
        name = "".join(name_chars)

        q1 = line.find('"')
        q2 = line.rfind('"')
        vars[name] = line[q1 + 1:q2]

    out = []

    for raw in prog_lines:
        s = strip_spaces(raw)
        if not s or s == ";":
            continue

        # print(...)
        if s.startswith("print("):
            inside = s[6:-2]  # between print( and );

            if inside.startswith("substr("):
                inner = inside[7:-1]
                name, offset, count, has_count = parse_substr_args(inner)
                out.append(get_substr(vars.get(name, ""), offset, count, has_count))
            else:
                out.append(vars.get(inside, ""))

        # substr(...)=...  (replacement)
        elif s.startswith("substr("):
            close = s.find(")")
            lhs_inner = s[7:close]
            rhs = s[close + 2:-1]  # after ")=" and before ';'

            name1, off1, cnt1, has_cnt1 = parse_substr_args(lhs_inner)

            # Evaluate RHS
            if rhs.startswith("substr("):
                rhs_inner = rhs[7:-1]
                name2, off2, cnt2, has_cnt2 = parse_substr_args(rhs_inner)
                new_value = get_substr(vars.get(name2, ""), off2, cnt2, has_cnt2)
            else:
                new_value = vars.get(rhs, "")

            base = vars.get(name1, "")
            nlen = len(base)
            start = off1 if off1 >= 0 else nlen + off1

            if not has_cnt1:
                end = nlen
            elif cnt1 >= 0:
                end = start + cnt1
            else:
                end = nlen + cnt1

            vars[name1] = base[:start] + new_value + base[end:]

        # name=...  (assignment)
        else:
            eq = s.find("=")
            lhs = s[:eq]
            rhs = s[eq + 1:-1]  # strip trailing ';'

            if rhs.startswith("substr("):
                inner = rhs[7:-1]
                name, offset, count, has_count = parse_substr_args(inner)
                vars[lhs] = get_substr(vars.get(name, ""), offset, count, has_count)
            else:
                vars[lhs] = vars.get(rhs, "")

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

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

