Deleting Digits

Time limit2sMemory limit128 MB

Summary

Given a digit string and a required count of each digit to delete, remove exactly that many occurrences of each digit to leave the numerically largest possible string.

Level: Medium6 of 10
Topics: Greedy, Stack, String, Simulation
Solved: No attempts yet

Problem

You are given a digit string with N digits. You must delete all of the specified digits from this string.

If the same digit appears more than once, you may choose which occurrence to delete. Deleting 5 from 12534 produces 1234, and deleting one 5 from 1253452 can produce either 123452 or 125342.

After deleting every specified digit, make the remaining digit string as large as possible. Given the original digit string and the digits that must be deleted, find the largest remaining digit string that can be made.

Input

The first line contains the N-digit string S. N is an integer between 1 and 1,000, inclusive.

The second line contains, without spaces, the digits that must be deleted. The number of digits to delete is less than N, and the input is guaranteed to allow all of those digits to be deleted from S.

Output

Print the largest remaining digit string that can be made after deleting all specified digits.

Examples6

Example 1
Input
```
12534
5
```
Expected output
```
1234
```
Example 2
Input
```
123123
1322
```
Expected output
```
31
```
Example 3
Input
```
112352
1123
```
Expected output
```
52
```
Example 4
Input
```
123456654321
612534
```
Expected output
```
654321
```
Example 5
Input
```
654321123456
612534
```
Expected output
```
654321
```
Example 6
Input
```
2654982765982365
2345978
```
Expected output
```
698265265
```