Censoring

Interview

Time limit1sMemory limit256 MB

Summary

Repeatedly delete the first occurrence of pattern T from string S until none remains and print the result.

Level: Medium5 of 10
Topics: Stack, String matching
Solved: No attempts yet

Problem

Farmer John subscribed to a magazine so that his cows have something to read while they wait during milking. The latest issue carries an article on how to cook the perfect steak, and John would rather his cows never see it.

John took every character of the magazine and joined it into one string $S$ of length at most $10^6$ . He now wants to censor the text by deleting the places where a string $T$ of length at most $100$ appears. The procedure is this. Find the first occurrence of $T$ in $S$ and delete it. Repeat, deleting the first occurrence of $T$ each time, until $T$ no longer appears in $S$ . A deletion joins the two halves around it, so an occurrence of $T$ that was not there before can appear.

Determine what $S$ is once the censoring is finished.

Input

The first line contains the string $S$ . The second line contains the string $T$ . The length of $T$ is at most the length of $S$ , and both $S$ and $T$ consist only of lower case letters a to z.

Output

Print the string $S$ after all deletions are finished. $S$ never becomes empty during the process.

Examples2

Example 1
Input
```
whatthemomooofun
moo
```
Expected output
```
whatthefun
```
Example 2
Input
```
banana
a
```
Expected output
```
bnn
```