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

395. "Binary Cat" Club
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



"Binary Cat" club is extremely popular among Berland citizens. Club is a pretty crowded place and some unpleasant incidents happen there from time to time. So the club management monitors their visitors thoroughly. Usual measures like "face control" are accompanied with so-called "logging". Each time visitor enters the club, the "" record is added to the log.  is the name of the person who just entered. Similarly the "" record is added when a person leaves the club. From time to time security adds records like "", where  is the number of the club guests present at the moment. At the moment the club was opened, it was empty. All records are added in the chronological order. If a person entered and exited the club several times, all these events are recorded. At the moment the club is closed some guests may still be there to participate in after-party. The club is big enough to contain any number of visitors at the same time.

However all this security precautions didn't help. Recently a big scandal happened in the club. The scandal was about the discussion of implementation details of Malhotra-Kumar-Maheshwari algorithm. Police requested the log of the events for the night of the incident from the club management. During logs archive inspection club personnel found out that logs for the night of the incident are not complete due to technical reasons. Some of the records in the log are missing, but all the remaining records are preserved in their original order.

Now club management wants to "polish" the log a bit, so that it looks plausible. They believe that the log looks plausible, if for the sequence of records in the log there is a sequence of actions which can happen in real life. For example, if the log contains a record that somebody leaves the club, the record about the same person entering the club should be present earlier in the log. Or, a person cannot enter the club the second time, if she did not leave the club after the first entry. The records "" should represent the actual number of guests in the club.

The club managers would like to add some random records to the log in such a way, that the relative order of existing records is preserved and the final log is plausible. Your task is to find minimal possible number of records to be added to the log and to create one of the variants of "polished" log.

Input
The first line of the input contains integer number N (1 ≤ N ≤ 200), where N is the number of existing records in the log. Following N lines contain records of the log, one per line. Each record has the form "", "" and "". The value of  is between 0 and 100, inclusive. All names have length between 1 and 16 characters and consist of only lowercase Latin letters.

Output
Write in the first line M, the minimal possible number of records in "polished" log. The following M lines should contain the records of the "polished" log in the same format they were given in the input. The limitations on the format of names and the number of visitors remain. If there are several solutions, choose any of them.

Example(s)
sample input
sample output
3
+ andrew
+ ilya
- mike
4
+ andrew
+ ilya
+ mike
- mike

sample input
sample output
1
= 2
3
+ first
+ second
= 2

sample input
sample output
3
- silentbob
- silentbob
= 1
6
+ silentbob
- silentbob
+ silentbob
- silentbob
+ silentbob
= 1

<|response|>
## 1. Abridged problem statement

We are given an incomplete chronological club log with records:

- `+ name`: `name` enters the club;
- `- name`: `name` leaves the club;
- `= k`: exactly `k` people are currently inside.

Initially the club is empty. Some records are missing, but the given records must remain in their original relative order.

We must insert the minimum possible number of records so that the final log is valid, and output one such completed log.

The first output number is the total number of records in the completed log.

---

## 2. Key observations

### Observation 1: Some fixes are forced

When processing records from left to right:

- If we see `+ x` but `x` is already inside, we must insert `- x` before it.
- If we see `- x` but `x` is not inside, we must insert `+ x` before it.
- If we see `= k`, the current number of visitors must become exactly `k`, so:
  - if current count is smaller, we must insert exactly `k - cnt` enter records;
  - if current count is larger, we must insert exactly `cnt - k` leave records.

So the number of insertions near an `= k` record is forced. The only choice is which people to add or remove.

---

### Observation 2: Names that never appear again can become anonymous

Suppose after some point a person’s name will never appear in the original log again.

Then we no longer care about their identity for future original records. They only affect the current number of people inside.

We maintain:

- named visitors: original names that may appear again later;
- anonymous visitors: people whose names no longer matter, but whose names we still store so we can output `- name` if needed;
- total count `cnt`.

---

### Observation 3: When increasing count at `= k`, choose useful names

If `cnt < k`, we need to insert enter records.

The best people to insert are absent original names whose next original event is `- x`.

Why?

If we insert `+ x` now, then the future `- x` becomes valid without needing another inserted `+ x`.

So one inserted record does two jobs.

Prefer such names whose future `- x` appears earliest.

If we still need more people, generate fresh unused names.

---

### Observation 4: When decreasing count at `= k`, remove least useful people

If `cnt > k`, we need to insert leave records.

Current visitors can be classified as:

1. Named visitors whose next event is `+ x`.

   They must be removed before that future `+ x` anyway, so remove them first.

2. Anonymous visitors.

   They have no future obligations, so removing them is safe.

3. Named visitors whose next event is `- x`.

   These are useful to keep, because their future `- x` can be consumed naturally.

If forced to remove people from category 3, remove those whose future `- x` is latest.

---

## 3. Full solution approach

### Preprocessing

Compress all original names to integer IDs.

For each name, store all positions where it appears in the original log. This allows us to quickly find the next occurrence of a name after the current position.

Also store the last occurrence of each name.

---

### State during processing

We scan the log from left to right and maintain:

```text
present[x] = whether original name x is currently inside as a named visitor
anonymous = stack of anonymous visitor names currently inside
cnt = total number of visitors currently inside
answer = completed log records
```

---

### Handling `+ x`

If `x` is already inside, insert `- x`.

Then output/process `+ x`.

If this is the last occurrence of `x` in the original log, put `x` into the anonymous stack. Otherwise mark `x` as present.

---

### Handling `- x`

If `x` is inside, output/process `- x`.

Otherwise, insert `+ x` immediately before it, then output/process `- x`.

This pair does not change `cnt`.

---

### Handling `= k`

If `cnt < k`, insert `k - cnt` enter records.

Priority:

1. absent original names whose next event is `- x`, sorted by earliest next occurrence;
2. fresh generated names.

If `cnt > k`, insert `cnt - k` leave records.

Priority:

1. present names whose next event is `+ x`, sorted by earliest next occurrence;
2. anonymous visitors;
3. present names whose next event is `- x`, sorted by latest next occurrence.

Then output the original `= k`.

---

### Correctness idea

For every `+ x` and `- x`, any violation forces exactly one inserted record, so the greedy fix is optimal.

For every `= k`, the required number of inserted records is exactly `|cnt - k|`, so only the choice of identities matters.

The greedy choices are optimal because:

- opening a person whose next event is `- x` saves a future insertion;
- closing a person whose next event is `+ x` saves a future insertion;
- anonymous people have no future value;
- people whose next event is `- x` are useful and should be kept as long as possible.

Thus after every processed prefix, the maintained state is at least as good for the remaining suffix as any alternative state with the same number of inserted records.

---

### Complexity

Let `D` be the number of distinct names.

`N <= 200`, so even simple scanning is fine.

Using binary search for next occurrences:

```text
Time:  O(N * D log N)
Memory: O(N + D)
```

---

## 4. C++ implementation with detailed comments

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

const int INF = 1e9;

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

    int n;
    cin >> n;

    /*
        type:
            0 -> '+'
            1 -> '-'
            2 -> '='

        arg:
            for '+' and '-' records: compressed name id
            for '=' records: required count
    */
    vector<int> type(n), arg(n);

    map<string, int> id;
    vector<string> names;

    for (int i = 0; i < n; i++) {
        char op;
        cin >> op;

        if (op == '=') {
            type[i] = 2;
            cin >> arg[i];
        } else {
            string s;
            cin >> s;

            if (!id.count(s)) {
                int new_id = (int)names.size();
                id[s] = new_id;
                names.push_back(s);
            }

            type[i] = (op == '+') ? 0 : 1;
            arg[i] = id[s];
        }
    }

    int d = (int)names.size();

    /*
        occ[x] contains all original log positions where name x appears.
    */
    vector<vector<int>> occ(d);

    for (int i = 0; i < n; i++) {
        if (type[i] != 2) {
            occ[arg[i]].push_back(i);
        }
    }

    /*
        last_pos[x] is the last original occurrence of name x.
    */
    vector<int> last_pos(d, -1);

    for (int x = 0; x < d; x++) {
        if (!occ[x].empty()) {
            last_pos[x] = occ[x].back();
        }
    }

    /*
        Return the first occurrence position of name x at or after position pos.
        If there is no such occurrence, return INF.
    */
    auto next_occ = [&](int x, int pos) {
        auto &v = occ[x];
        auto it = lower_bound(v.begin(), v.end(), pos);
        if (it == v.end()) return INF;
        return *it;
    };

    /*
        Fresh generated names must not collide with original names.
        We generate lowercase strings: a, b, ..., z, aa, ab, ...
    */
    set<string> used_original(names.begin(), names.end());
    vector<int> digits(1, 0);

    auto next_fresh = [&]() mutable {
        while (true) {
            string s;
            for (int v : digits) {
                s.push_back(char('a' + v));
            }

            int p = (int)digits.size() - 1;

            while (p >= 0 && digits[p] == 25) {
                digits[p] = 0;
                p--;
            }

            if (p < 0) {
                digits.assign(digits.size() + 1, 0);
            } else {
                digits[p]++;
            }

            if (!used_original.count(s)) {
                return s;
            }
        }
    };

    /*
        present[x] == true means original name x is currently inside
        as a tracked named visitor.

        Anonymous visitors are stored by name in anon.
        They may include:
            - generated fresh names;
            - original names that will never appear again later.
    */
    vector<bool> present(d, false);
    vector<string> anon;

    int cnt = 0;
    vector<string> answer;

    auto open_named = [&](int x) {
        answer.push_back("+ " + names[x]);
        present[x] = true;
        cnt++;
    };

    auto close_named = [&](int x) {
        answer.push_back("- " + names[x]);
        present[x] = false;
        cnt--;
    };

    auto open_anon = [&](const string &s) {
        answer.push_back("+ " + s);
        anon.push_back(s);
        cnt++;
    };

    auto close_anon = [&]() {
        string s = anon.back();
        anon.pop_back();
        answer.push_back("- " + s);
        cnt--;
    };

    for (int i = 0; i < n; i++) {
        int t = type[i];
        int a = arg[i];

        if (t == 0) {
            /*
                Original record: + name
            */
            if (present[a]) {
                /*
                    Cannot enter twice without leaving.
                    Insert '- name' before this '+ name'.
                */
                close_named(a);
            }

            /*
                Now process the original '+ name'.
                If this is the last occurrence of the name, identity no longer
                matters for future original records, so store it as anonymous.
            */
            if (last_pos[a] == i) {
                open_anon(names[a]);
            } else {
                open_named(a);
            }
        } else if (t == 1) {
            /*
                Original record: - name
            */
            if (present[a]) {
                /*
                    The person is inside, so the leave is valid.
                */
                close_named(a);
            } else {
                /*
                    The person is absent.
                    Insert '+ name' immediately before '- name'.
                    Net change in cnt is zero.
                */
                answer.push_back("+ " + names[a]);
                answer.push_back("- " + names[a]);
            }
        } else {
            /*
                Original record: = k
            */
            int k = a;

            if (cnt < k) {
                /*
                    Need to insert k - cnt enter records.
                */
                int need = k - cnt;

                vector<pair<int, int>> candidates;

                for (int x = 0; x < d; x++) {
                    if (!present[x]) {
                        int nx = next_occ(x, i);

                        /*
                            If the next event of x is '- x', opening x now
                            will make that future leave valid.
                        */
                        if (nx != INF && type[nx] == 1) {
                            candidates.push_back({nx, x});
                        }
                    }
                }

                sort(candidates.begin(), candidates.end());

                int done = 0;

                for (auto [pos, x] : candidates) {
                    if (done == need) break;
                    open_named(x);
                    done++;
                }

                /*
                    Fill remaining required people with fresh names.
                */
                while (done < need) {
                    open_anon(next_fresh());
                    done++;
                }
            } else if (cnt > k) {
                /*
                    Need to insert cnt - k leave records.
                */
                int need = cnt - k;

                vector<pair<int, int>> liabilities;
                vector<pair<int, int>> useful;

                for (int x = 0; x < d; x++) {
                    if (present[x]) {
                        int nx = next_occ(x, i);

                        if (nx != INF && type[nx] == 0) {
                            /*
                                This person's next original event is '+ x',
                                so they must leave before that anyway.
                            */
                            liabilities.push_back({nx, x});
                        } else {
                            /*
                                Usually next event is '- x', so this person
                                is useful to keep.
                            */
                            useful.push_back({nx, x});
                        }
                    }
                }

                /*
                    Close liabilities with earliest future '+ x' first.
                */
                sort(liabilities.begin(), liabilities.end());

                /*
                    If we must close useful people, close those whose future
                    event is latest.
                */
                sort(useful.begin(), useful.end(), greater<pair<int, int>>());

                int remaining = need;

                for (auto [pos, x] : liabilities) {
                    if (remaining == 0) break;
                    close_named(x);
                    remaining--;
                }

                while (remaining > 0 && !anon.empty()) {
                    close_anon();
                    remaining--;
                }

                for (auto [pos, x] : useful) {
                    if (remaining == 0) break;
                    close_named(x);
                    remaining--;
                }
            }

            /*
                Now cnt == k, so the equality record is valid.
            */
            answer.push_back("= " + to_string(k));
        }
    }

    cout << answer.size() << '\n';

    for (const string &line : answer) {
        cout << line << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
from bisect import bisect_left


INF = 10 ** 9


def main():
    input_data = sys.stdin.read().strip().splitlines()

    n = int(input_data[0])

    # type[i]:
    #   0 -> '+'
    #   1 -> '-'
    #   2 -> '='
    #
    # arg[i]:
    #   for '+' and '-': compressed name id
    #   for '=': required count
    rec_type = [0] * n
    rec_arg = [0] * n

    name_id = {}
    names = []

    for i in range(n):
        parts = input_data[i + 1].split()
        op = parts[0]

        if op == "=":
            rec_type[i] = 2
            rec_arg[i] = int(parts[1])
        else:
            name = parts[1]

            if name not in name_id:
                name_id[name] = len(names)
                names.append(name)

            rec_type[i] = 0 if op == "+" else 1
            rec_arg[i] = name_id[name]

    d = len(names)

    # occ[x] stores all original positions where name x appears.
    occ = [[] for _ in range(d)]

    for i in range(n):
        if rec_type[i] != 2:
            occ[rec_arg[i]].append(i)

    # last_pos[x] is the last original occurrence of name x.
    last_pos = [-1] * d

    for x in range(d):
        if occ[x]:
            last_pos[x] = occ[x][-1]

    def next_occ(x, pos):
        """
        Return first original occurrence of name x at or after pos.
        If it does not exist, return INF.
        """
        arr = occ[x]
        j = bisect_left(arr, pos)

        if j == len(arr):
            return INF

        return arr[j]

    # Fresh names must not collide with original names.
    used_original = set(names)

    # Base-26 counter:
    # [0] -> a, [1] -> b, ..., [25] -> z, [0,0] -> aa, ...
    digits = [0]

    def next_fresh():
        """
        Generate a lowercase name that does not appear in the original input.
        Generated names are unique because the counter only moves forward.
        """
        nonlocal digits

        while True:
            s = "".join(chr(ord("a") + x) for x in digits)

            # Increment base-26 counter.
            p = len(digits) - 1

            while p >= 0 and digits[p] == 25:
                digits[p] = 0
                p -= 1

            if p < 0:
                digits = [0] * (len(digits) + 1)
            else:
                digits[p] += 1

            if s not in used_original:
                return s

    # present[x] is True if original name x is currently inside
    # as a tracked named visitor.
    present = [False] * d

    # Anonymous visitors currently inside.
    # We keep their names so we can output '- name' later.
    anonymous = []

    cnt = 0
    answer = []

    def open_named(x):
        """
        Add original name x as a tracked visitor.
        """
        nonlocal cnt
        answer.append("+ " + names[x])
        present[x] = True
        cnt += 1

    def close_named(x):
        """
        Remove tracked original name x.
        """
        nonlocal cnt
        answer.append("- " + names[x])
        present[x] = False
        cnt -= 1

    def open_anonymous(name):
        """
        Add an anonymous visitor.
        """
        nonlocal cnt
        answer.append("+ " + name)
        anonymous.append(name)
        cnt += 1

    def close_anonymous():
        """
        Remove the most recently added anonymous visitor.
        """
        nonlocal cnt
        name = anonymous.pop()
        answer.append("- " + name)
        cnt -= 1

    for i in range(n):
        t = rec_type[i]
        a = rec_arg[i]

        if t == 0:
            # Original record: + name

            if present[a]:
                # Cannot enter twice without leaving.
                # Insert '- name' first.
                close_named(a)

            # Process original '+ name'.
            # If this is the last occurrence, identity no longer matters.
            if last_pos[a] == i:
                open_anonymous(names[a])
            else:
                open_named(a)

        elif t == 1:
            # Original record: - name

            if present[a]:
                # The person is currently inside, so this leave is valid.
                close_named(a)
            else:
                # Person is absent.
                # Insert '+ name' immediately before '- name'.
                # Net change in cnt is zero.
                answer.append("+ " + names[a])
                answer.append("- " + names[a])

        else:
            # Original record: = k
            k = a

            if cnt < k:
                # Need to insert k - cnt enter records.
                need = k - cnt

                candidates = []

                for x in range(d):
                    if not present[x]:
                        nx = next_occ(x, i)

                        # If next event is '- x', opening x now helps later.
                        if nx != INF and rec_type[nx] == 1:
                            candidates.append((nx, x))

                # Prefer candidates whose useful future leave is earliest.
                candidates.sort()

                done = 0

                for _, x in candidates:
                    if done == need:
                        break

                    open_named(x)
                    done += 1

                # Fill the remaining required count with fresh names.
                while done < need:
                    open_anonymous(next_fresh())
                    done += 1

            elif cnt > k:
                # Need to insert cnt - k leave records.
                need = cnt - k

                liabilities = []
                useful = []

                for x in range(d):
                    if present[x]:
                        nx = next_occ(x, i)

                        if nx != INF and rec_type[nx] == 0:
                            # Next original event is '+ x',
                            # so x must leave before it anyway.
                            liabilities.append((nx, x))
                        else:
                            # Usually next event is '- x',
                            # so this person is useful to keep.
                            useful.append((nx, x))

                # Close people whose next event is '+ x' first.
                liabilities.sort()

                # If forced to close useful people,
                # close those with latest future event first.
                useful.sort(reverse=True)

                remaining = need

                for _, x in liabilities:
                    if remaining == 0:
                        break

                    close_named(x)
                    remaining -= 1

                # Then close anonymous visitors.
                while remaining > 0 and anonymous:
                    close_anonymous()
                    remaining -= 1

                # Finally close useful named visitors if unavoidable.
                for _, x in useful:
                    if remaining == 0:
                        break

                    close_named(x)
                    remaining -= 1

            # Now cnt == k, so the equality record is valid.
            answer.append("= " + str(k))

    print(len(answer))

    for line in answer:
        print(line)


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