Censoring

Interview

Time limit1sMemory limit256 MB

Summary

Repeatedly delete the first occurrence of T from S, including matches formed by earlier deletions, and print what remains.

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

Problem

Farmer John subscribed to a housekeeping magazine so his cows have something to read while they wait to be milked. The latest issue carries an article on cooking the perfect steak, and John would rather his cows never see it.

John concatenated all of the magazine text into a string $S$ of length at most $10^6$ . He now wants to censor it by deleting the offending substring $T$ . He does it like this. Find the first occurrence of $T$ in $S$ and delete it. Repeat the same step, always deleting the first remaining occurrence, until $T$ no longer occurs in $S$ . One deletion can create a new occurrence of $T$ that was not there before.

Report the contents of $S$ 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 complete. No input makes $S$ become empty during the deletion process.

Examples5

Example 1
Input
```
whatthemomooofun
moo
```
Expected output
```
whatthefun
```
Example 2
Input
```
abcdefghij
xyz
```
Expected output
```
abcdefghij
```
Example 3
Input
```
abc
abd
```
Expected output
```
abc
```
Example 4
Input
```
banana
a
```
Expected output
```
bnn
```
Example 5
Input
```
aaaaaaa
aaa
```
Expected output
```
a
```