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

```cpp
#include <bits/stdc++.h>

using namespace std;

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) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<string> init_lines, prog_lines;
map<string, string> vars;

void read() {
    cin >> n >> m;
    cin.ignore();

    vector<string> all_lines;
    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_lines.push_back(line);
        }
    }

    init_lines.assign(all_lines.begin(), all_lines.begin() + n);
    prog_lines.assign(all_lines.begin() + n, all_lines.begin() + n + m);
}

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

substr_args parse_substr_args(const string& s) {
    int comma1 = s.find(',');
    string name = s.substr(0, comma1);
    string rest = s.substr(comma1 + 1);
    int comma2 = rest.find(',');
    if(comma2 == (int)string::npos) {
        return {name, stoi(rest), 0, false};
    }
    return {
        name, stoi(rest.substr(0, comma2)), stoi(rest.substr(comma2 + 1)), true
    };
}

string get_substr(const string& str, int offset, int count, bool has_count) {
    int len = str.size();
    int start = offset >= 0 ? offset : len + offset;
    int end;
    if(!has_count) {
        end = len;
    } else if(count >= 0) {
        end = start + count;
    } else {
        end = len + count;
    }
    return str.substr(start, end - start);
}

string strip_spaces(const string& s) {
    string result;
    for(char c: s) {
        if(c != ' ') {
            result += c;
        }
    }
    return result;
}

void solve() {
    // This is mostly an implementation problem, which does require a fair bit
    // of parsing.

    for(auto& line: init_lines) {
        int dollar = line.find('$');
        int i = dollar;
        string name;
        while(i < (int)line.size() &&
              (isalnum(line[i]) || line[i] == '$' || line[i] == '_')) {
            name += line[i++];
        }
        int q1 = line.find('"');
        int q2 = line.rfind('"');
        vars[name] = line.substr(q1 + 1, q2 - q1 - 1);
    }

    for(auto& raw_line: prog_lines) {
        string line = strip_spaces(raw_line);
        if(line.empty() || line == ";") {
            continue;
        }

        if(line.substr(0, 6) == "print(") {
            string content = line.substr(6, line.size() - 8);
            if(content.substr(0, 7) == "substr(") {
                string inner = content.substr(7, content.size() - 8);
                auto [name, offset, count, has_count] =
                    parse_substr_args(inner);
                cout << get_substr(vars[name], offset, count, has_count)
                     << "\n";
            } else {
                cout << vars[content] << "\n";
            }
        } else if(line.substr(0, 7) == "substr(") {
            int close_paren = line.find(')');
            string lhs_inner = line.substr(7, close_paren - 7);
            string rhs =
                line.substr(close_paren + 2, line.size() - close_paren - 3);

            auto [name1, offset1, count1, has_count1] =
                parse_substr_args(lhs_inner);

            string new_value;
            if(rhs.substr(0, 7) == "substr(") {
                string rhs_inner = rhs.substr(7, rhs.size() - 8);
                auto [name2, offset2, count2, has_count2] =
                    parse_substr_args(rhs_inner);
                new_value =
                    get_substr(vars[name2], offset2, count2, has_count2);
            } else {
                new_value = vars[rhs];
            }

            string& str = vars[name1];
            int len = str.size();
            int start = offset1 >= 0 ? offset1 : len + offset1;
            int end;
            if(!has_count1) {
                end = len;
            } else if(count1 >= 0) {
                end = start + count1;
            } else {
                end = len + count1;
            }

            str = str.substr(0, start) + new_value + str.substr(end);
        } else {
            int eq = line.find('=');
            string lhs = line.substr(0, eq);
            string rhs = line.substr(eq + 1, line.size() - eq - 2);

            if(rhs.substr(0, 7) == "substr(") {
                string rhs_inner = rhs.substr(7, rhs.size() - 8);
                auto [name2, offset2, count2, has_count2] =
                    parse_substr_args(rhs_inner);
                vars[lhs] =
                    get_substr(vars[name2], offset2, count2, has_count2);
            } else {
                vars[lhs] = vars[rhs];
            }
        }
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    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()
```
