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

296. Sasha vs. Kate
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



During the regular Mars's World Finals Subregional Programming Contest a boy Sasha lost N "Mars" bars of chocolate to a girl Kate. But for two years already Sasha does not hurry to pay his debt. And now Sasha and Kate decided that Sasha will give Kate P chocolate bars, where number P can be obtained from the number N by removing exactly K decimal digits. Sasha generously let Kate to choose digits to be removed. Your task is to find out how many bars Sasha will give Kate. Of course Kate will choose K digits from the number N in such a way that the resulting number P would be maximal.

Input
The first line of the input file contains two integer numbers N and K (1≤ N≤ 101000; 0≤ K≤ 999). Number K is strictly less than the number of digits in N. N will not have any leading zeros.

Output
Output the unknown P.

Example(s)
sample input
sample output
1992 2
99

sample input
sample output
1000 2
10

<|response|>
## 1. Abridged Problem Statement

Given a decimal number `N` and an integer `K`, remove exactly `K` digits from `N` while keeping the relative order of the remaining digits. Among all possible results, output the maximum possible number.

`N` can be very large, so it must be processed as a string.

---

## 2. Key Observations

### Observation 1: The order of remaining digits cannot change

Removing digits from `N` means we are choosing a subsequence of its digits.

For example, from:

```text
1992
```

If we remove `2` digits, we need to keep `2` digits in their original order.

Possible results include:

```text
19, 19, 12, 99, 92, 92
```

The maximum is:

```text
99
```

---

### Observation 2: All valid answers have the same length

If `N` has length `D`, and we remove exactly `K` digits, then the answer always has length:

```text
D - K
```

Therefore, maximizing the final number is the same as maximizing it lexicographically from left to right.

That means we want the leftmost digits to be as large as possible.

---

### Observation 3: A smaller digit before a larger digit should be removed if possible

Suppose while scanning the number we already kept digit `3`, and now we see digit `8`.

If we still have deletions available, replacing `3` with `8` at an earlier position makes the final number larger.

So we should delete smaller previous digits when a larger digit appears after them.

This greedy can be realized either with a monotonic stack, or by tracking, per
answer position, the set of source indices that could end the current optimal
prefix.

---

## 3. Full Solution Approach

We build the answer one position at a time, always choosing the largest digit
reachable given the remaining deletion budget.

The C++ implementation tracks a set of candidate source indices
(`valid_states`):

1. The first answer digit may come from any index in `[0, K]`, because at most
   `K` digits may be deleted before it. Take the largest digit in that window;
   every index attaining it becomes a candidate.
2. For a later answer position `l`, a candidate index `i` has already spent
   `i - l + 1` deletions to reach there, so from it the next digit can land on
   any index up to `i + (K - (i - l + 1)) + 1`. Mark the union of these reaches
   in `can_visit`, scan it for the maximal digit, and keep the matching indices
   as candidates for the next position.

Iterating the candidate list in reversed (descending index) order lets the
inner loop stop as soon as it reaches an already-marked index, so each
next-layer index is marked once.

The Python implementation uses the equivalent monotonic-stack formulation: scan
the digits of `N` left to right, maintaining a stack of digits representing the
best prefix so far. For each digit `d`, while the stack is nonempty, deletions
remain, and the stack top is smaller than `d`, pop the stack; then push `d`.
After scanning, if deletions remain (the digits are already non-increasing),
remove the rest from the end. Output the first `len(N) - K` digits.

---

### Example

Input:

```text
1992 2
```

Process (monotonic stack):

```text
digit = 1
stack = 1

digit = 9
1 < 9, delete 1
stack = 9

digit = 9
stack = 99

digit = 2
stack = 992
```

We deleted only one digit so far, but need to delete `2` digits total.

Remove one more digit from the end:

```text
99
```

Answer:

```text
99
```

---

### Correctness Intuition

Whenever a larger digit appears, it is always beneficial to move it as far left as possible by deleting smaller digits before it, as long as we still have deletions available.

The greedy does exactly this. It never deletes a digit unless a better larger digit can replace it earlier in the result.

If no such larger digit appears, then the current digits are already in the best possible order, so remaining deletions should be made from the end.

Thus, the algorithm constructs the lexicographically largest subsequence of length `len(N) - K`, which is the maximum possible number.

---

### Complexity

Let `D = len(N)`.

The monotonic-stack version pushes and pops each digit at most once, giving
`O(D)`. The layered C++ version processes at most `D` answer positions, marking
each next index once per position, so `O(D^2)` worst case — easily within the
limits for `D ≤ 1000`.

```text
Memory complexity: O(D)
```

---

## 4. C++ Implementation with Detailed Comments

```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 k;
string n;

void read() { cin >> n >> k; }

void solve() {
    // We delete exactly K digits and keep the remaining len = |N| - K digits
    // in order, choosing them so the resulting number is maximal. Build the
    // answer greedily one digit at a time: for each output position take the
    // largest digit reachable, and keep every source index that attains it as
    // a candidate start for the next digit.
    //
    // The first digit may come from any index in [0, K], since len - 1 digits
    // must remain after it. For a later position l, a candidate index i has
    // already used i - l + 1 deletions to get there, so from it the next digit
    // can reach any index up to i + (K - (i - l + 1)) + 1 = K + l. We mark the
    // union of these reaches in can_visit, scan it for the best digit, and keep
    // the indices that match it as the candidate set for the following
    // position.

    string ans;
    vector<int> valid_states;

    char best = 0;
    for(int i = 0; i <= k; i++) {
        best = max(best, n[i]);
    }

    for(int i = 0; i <= k; i++) {
        if(n[i] == best) {
            valid_states.push_back(i);
        }
    }

    ans.push_back(best);

    int len = n.size() - k;
    for(int l = 1; l < len; l++) {
        vector<bool> can_visit(n.size(), false);
        reverse(valid_states.begin(), valid_states.end());
        for(int i: valid_states) {
            int ck = i - l + 1;
            for(int j = 0; j <= k - ck; j++) {
                int nxt = i + j + 1;
                if(nxt >= (int)n.size() || can_visit[nxt]) {
                    break;
                }
                can_visit[nxt] = true;
            }
        }

        char best = 0;
        for(int i = 0; i < (int)n.size(); i++) {
            if(can_visit[i]) {
                best = max(best, n[i]);
            }
        }

        vector<int> new_valid_states;
        for(int i = 0; i < (int)n.size(); i++) {
            if(n[i] == best && can_visit[i]) {
                new_valid_states.push_back(i);
            }
        }

        ans.push_back(best);
        valid_states = new_valid_states;
    }

    cout << ans << '\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys


def main():
    data = sys.stdin.read().split()

    if not data:
        return

    # N can be very large, so read it as a string.
    n = data[0]

    # K digits must be removed.
    k = int(data[1])

    # Final answer length.
    keep = len(n) - k

    # Stack storing the best digits chosen so far.
    stack = []

    # Number of digits removed so far.
    removed = 0

    # Scan digits from left to right.
    for digit in n:
        """
        If the previous chosen digit is smaller than the current digit,
        deleting it allows the current larger digit to move left,
        making the final number larger.
        """
        while stack and removed < k and stack[-1] < digit:
            stack.pop()
            removed += 1

        # Keep the current digit.
        stack.append(digit)

    """
    If not all deletions were used, remove remaining digits from the end.
    Removing from the end is optimal when no larger digit appears later.
    """
    extra = k - removed

    if extra > 0:
        stack = stack[:-extra]

    # The answer must contain exactly keep digits.
    answer = ''.join(stack[:keep])

    sys.stdout.write(answer)


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