Bug Catcher

Time limit1sMemory limit128 MB

Summary

For each code line, repeatedly remove the first occurrence of a given bug string until no occurrence remains, then print the result.

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

Problem

Not every bug is an insect. Some bugs are a developer's nightmare — the kind people mean when they say "a bug was found in the program you wrote." And as you know, no matter how many you remove, more keep appearing.

Recently a rather handy tool called "Bug Catcher" appeared. It finds and removes every bug in your source code. Your job is to implement this "Bug Catcher": given the source code, keep deleting the string that represents a bug until none remain.

Input

The input consists of several test cases and continues until the end of the file.

Each test case begins with one line containing an integer $T$ ( $0 \le T \le 100\,000$ ), a single space, and a string $B$ that represents a bug. The next $T$ lines each contain one line of source code from which bugs must be removed.

Each source-code line has length between $0$ and $2\,000\,000$ characters. The bug string $B$ consists of $1$ to $1000$ uppercase English letters. Matching is case-sensitive: only substrings exactly equal to $B$ count as bugs.

Output

For each source-code line, repeatedly delete the first occurrence of $B$ until $B$ no longer appears, and print the resulting line.

No bug may remain in the output. Every other character, including whitespace, must be printed exactly as it appeared in the input.

Examples8

Example 1

Input

7 BUG
print "No bugs here..."

void hello() {
BUGBUG
  printfBUG("Hello, world!\n");
}

1 ERR
wriERRERRtelERRn("Hello E-R-R");

Expected output

print "No bugs here..."

void hello() {

  printf("Hello, world!\n");
}

writeln("Hello E-R-R");

Example 2
Input
```
0 X
2 A
BANANA
AAAA
```
Expected output
```
BNN
```
Example 3
Input
```
2 AA
AAAAA
AAAA
```
Expected output
```
A
```
Example 4
Input
```
1 BUG
BUBUGG
```
Expected output
Example 5
Input
```
1 ABA
ABABABA
```
Expected output
```
B
```

Example 6

Input

1 XYZ
hello, world! no bugs here.

Expected output

hello, world! no bugs here.

Example 7
Input
```
1 BUG
BUGhelloBUGworldBUG
```
Expected output
```
helloworld
```
Example 8
Input
```
1 BUG
   BUG spaces   
```
Expected output
```
    spaces   
```