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

```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;
vector<int> rec_type;
vector<int> rec_arg;
vector<string> names;

void read() {
    cin >> n;
    rec_type.assign(n, 0);
    rec_arg.assign(n, 0);
    map<string, int> id;
    for(int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if(c == '=') {
            rec_type[i] = 2;
            cin >> rec_arg[i];
        } else {
            rec_type[i] = (c == '+') ? 0 : 1;
            string nm;
            cin >> nm;
            auto it = id.find(nm);
            if(it == id.end()) {
                int k = names.size();
                id[nm] = k;
                names.push_back(nm);
                rec_arg[i] = k;
            } else {
                rec_arg[i] = it->second;
            }
        }
    }
}

void solve() {
    // One left-to-right pass over the records, emitting each original
    // record and only inserting an extra one when the next record cannot
    // be consumed as-is. present[x] = 1 for the named guests inside whose
    // name still appears later in the input (others fold into the
    // anonymous bag), anon is a stack of the names currently filling the
    // anonymous slots, and cnt = (# present named) + anon.size(). Leaving
    // is a set operation, so person intervals can cross and a nested-
    // bracket model would be wrong; the genuinely hard cells are '= k'
    // because they pin the exact headcount.
    //
    // Name collapse: when we place a '+ x' and last_at[x] == i, x's name
    // never appears again so that guest can be treated as anonymous and
    // pushed onto anon instead of into present. This is the trick that
    // keeps the state size linear - a brute force that kept the present
    // set explicit would generate every subset while closing m guests at
    // a single '= 0' cell, blowing up to 2^m states.
    //
    // The forced cases first. '+ x' with x already inside is a '++' that
    // needs a separator: emit '- x' first, then the '+ x'. '- x' with x
    // absent needs a feed: emit '+ x' first, then the '- x' (the pair
    // leaves cnt unchanged). Everything else just consumes the record.
    //
    // The interesting cells are '= k'. Each insert there can do "double
    // duty" - serve the cell AND a future record - if we pick the right
    // person. The two priorities below are exactly the ones that fuse the
    // double uses; each is a local exchange argument over the next
    // occurrence of each name.
    //
    // '= k' below cnt evicts in this order. Guests whose next record is
    // '+ x' go first, in ascending position of that '+ x': we would have
    // had to evict them before that record anyway, so the insert here IS
    // the separator we would have paid later (one insert serves two
    // needs). Then anon, popped LIFO: anonymous guests have no future
    // obligation, so closing one costs exactly one insert and nothing
    // else. Then the remaining named guests, whose next record is '- x',
    // by descending position of that close: evicting one of these breaks
    // a natural pair (the future '- x' will need a feed), so each is
    // worth one extra insert later; among them the latest close is the
    // most likely to be broken anyway by some later '= k', so it is the
    // least valuable to keep.
    //
    // '= k' above cnt admits feeds before fresh guests. A name x is a
    // feed candidate iff x is absent and its next record is '- x';
    // admitting x now means the inserted '+ x' is reused by that '- x'
    // for free (one insert serves two needs). Earliest-close candidates
    // first because their entries get redeemed soonest. Anything left
    // over draws a name from next_fresh(), an enumerator of unused
    // lowercase strings.

    int d = names.size();
    vector<vector<int>> occ(d);
    for(int i = 0; i < n; i++) {
        if(rec_type[i] != 2) {
            occ[rec_arg[i]].push_back(i);
        }
    }
    vector<int> last_at(d, -1);
    for(int x = 0; x < d; x++) {
        if(!occ[x].empty()) {
            last_at[x] = occ[x].back();
        }
    }
    auto next_occ = [&](int x, int from) {
        auto& v = occ[x];
        auto it = lower_bound(v.begin(), v.end(), from);
        return it == v.end() ? INT_MAX : *it;
    };

    set<string> used_names(names.begin(), names.end());
    vector<int> digits(1, 0);
    auto next_fresh = [&]() {
        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_names.count(s)) {
                return s;
            }
        }
    };

    vector<char> present(d, 0);
    vector<string> anon;
    int cnt = 0;
    vector<string> out;

    auto open_named = [&](int x) {
        out.push_back("+ " + names[x]);
        present[x] = 1;
        cnt++;
    };
    auto close_named = [&](int x) {
        out.push_back("- " + names[x]);
        present[x] = 0;
        cnt--;
    };
    auto open_anon = [&](const string& nm) {
        out.push_back("+ " + nm);
        anon.push_back(nm);
        cnt++;
    };
    auto close_anon = [&]() {
        out.push_back("- " + anon.back());
        anon.pop_back();
        cnt--;
    };

    for(int i = 0; i < n; i++) {
        int t = rec_type[i], a = rec_arg[i];
        if(t == 0) {
            if(present[a]) {
                close_named(a);
            }
            if(last_at[a] == i) {
                open_anon(names[a]);
            } else {
                open_named(a);
            }
        } else if(t == 1) {
            if(present[a]) {
                close_named(a);
            } else {
                out.push_back("+ " + names[a]);
                out.push_back("- " + names[a]);
            }
        } else {
            int k = a;
            if(cnt < k) {
                int need = k - cnt;
                vector<pair<int, int>> cand;
                for(int x = 0; x < d; x++) {
                    if(!present[x]) {
                        int nx = next_occ(x, i);
                        if(nx != INT_MAX && rec_type[nx] == 1) {
                            cand.push_back({nx, x});
                        }
                    }
                }
                sort(cand.begin(), cand.end());
                int done = 0;
                for(auto& pr: cand) {
                    if(done >= need) {
                        break;
                    }
                    open_named(pr.second);
                    done++;
                }
                while(done < need) {
                    open_anon(next_fresh());
                    done++;
                }
            } else if(cnt > k) {
                int need = cnt - k;
                vector<pair<int, int>> liab, useful;
                for(int x = 0; x < d; x++) {
                    if(present[x]) {
                        int nx = next_occ(x, i);
                        if(nx != INT_MAX && rec_type[nx] == 0) {
                            liab.push_back({nx, x});
                        } else {
                            useful.push_back({nx, x});
                        }
                    }
                }
                sort(liab.begin(), liab.end());
                sort(useful.begin(), useful.end(), greater<>());
                int rem = need;
                for(auto& pr: liab) {
                    if(rem == 0) {
                        break;
                    }
                    close_named(pr.second);
                    rem--;
                }
                while(rem > 0 && !anon.empty()) {
                    close_anon();
                    rem--;
                }
                for(auto& pr: useful) {
                    if(rem == 0) {
                        break;
                    }
                    close_named(pr.second);
                    rem--;
                }
            }
            out.push_back("= " + to_string(k));
        }
    }

    cout << out.size() << '\n';
    for(auto& line: out) {
        cout << line << '\n';
    }
}

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

```python
import sys
from bisect import bisect_left


def main():
    data = sys.stdin.read().strip().splitlines()
    n = int(data[0])

    rec_type = [0] * n
    rec_arg = [0] * n
    name_id = {}
    names = []

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

        if op == "=":
            rec_type[i] = 2
            rec_arg[i] = int(parts[1])
        else:
            nm = parts[1]
            if nm not in name_id:
                name_id[nm] = len(names)
                names.append(nm)
            rec_type[i] = 0 if op == "+" else 1
            rec_arg[i] = name_id[nm]

    d = len(names)
    occ = [[] for _ in range(d)]

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

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

    def next_occ(x, pos):
        arr = occ[x]
        j = bisect_left(arr, pos)
        if j == len(arr):
            return 10**9
        return arr[j]

    used_original = set(names)
    digits = [0]

    def next_fresh():
        nonlocal digits
        while True:
            s = "".join(chr(ord("a") + v) for v in digits)
            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 = [False] * d
    anon = []
    cnt = 0
    out = []

    def open_named(x):
        nonlocal cnt
        out.append("+ " + names[x])
        present[x] = True
        cnt += 1

    def close_named(x):
        nonlocal cnt
        out.append("- " + names[x])
        present[x] = False
        cnt -= 1

    def open_anon(nm):
        nonlocal cnt
        out.append("+ " + nm)
        anon.append(nm)
        cnt += 1

    def close_anon():
        nonlocal cnt
        nm = anon.pop()
        out.append("- " + nm)
        cnt -= 1

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

        if t == 0:
            if present[a]:
                close_named(a)
            if last_at[a] == i:
                open_anon(names[a])
            else:
                open_named(a)

        elif t == 1:
            if present[a]:
                close_named(a)
            else:
                out.append("+ " + names[a])
                out.append("- " + names[a])

        else:
            k = a
            if cnt < k:
                need = k - cnt
                candidates = []
                for x in range(d):
                    if not present[x]:
                        nx = next_occ(x, i)
                        if nx != 10**9 and rec_type[nx] == 1:
                            candidates.append((nx, x))
                candidates.sort()
                done = 0
                for _, x in candidates:
                    if done == need:
                        break
                    open_named(x)
                    done += 1
                while done < need:
                    open_anon(next_fresh())
                    done += 1

            elif cnt > k:
                need = cnt - k
                liabilities = []
                useful = []
                for x in range(d):
                    if present[x]:
                        nx = next_occ(x, i)
                        if nx != 10**9 and rec_type[nx] == 0:
                            liabilities.append((nx, x))
                        else:
                            useful.append((nx, x))
                liabilities.sort()
                useful.sort(reverse=True)
                rem = need
                for _, x in liabilities:
                    if rem == 0:
                        break
                    close_named(x)
                    rem -= 1
                while rem > 0 and anon:
                    close_anon()
                    rem -= 1
                for _, x in useful:
                    if rem == 0:
                        break
                    close_named(x)
                    rem -= 1

            out.append("= " + str(k))

    print(len(out))
    print("\n".join(out))


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