Petya found an old telegraph machine in the attic and attached to it an ingenious device that can print a certain word on the telegraph tape (let's denote it as X). Petino's device can print this word on the tape any number of times. Petya can force the device to print any other message on the tape, but for this he needs to disassemble his ingenious device, and after that he will no longer be able to print message X. And most importantly, printing even one character of another message will require more effort from Petya, than printing the word X on tape using a contraption.
Petya wants to make it seem to everyone that he received a message Z by telegraph. To do this, he can (strictly in this sequence):
- print message X as many times as you want
- take apart the contraption and type something else character-by-character (let's call it Y)
- tear off and discard the beginning of the tape so that the remaining tape prints exactly the message Z
Since typing individual characters of message Y is quite difficult, Petya wants message Y to contain as few characters as possible.
For a better understanding of the task, see examples and explanations for them.
Input
The first line contains the word X, which Petya can type as many times as he likes with the ingenious device. The second line contains the message Z that Petya wants to receive. Each message consists only of small Latin letters and has a maximum length of 100 characters.
Imprint
Print the shortest message Y that Petya will have to type manually.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
mama
amamam |
m |
First, Petya will type the word mama twice, then he will print the letter m to it, and then he will cut off and discard the three initial characters (mam). The answer is the letter m, printed separately. |
| 2 |
ura
mura |
mura |
It would seem that Petya should first type the letter m, and then the word ura, which he can type. However, in order to type m, he would have to disassemble his device, and he would also have to type ura character-by-character. |
| 3 |
computer
comp |
comp |
It would seem that Petya can type the word computer, and then cut off and throw away the end — however, he cannot do this, because he can only cut and discard the beginning of the tape. |
| 4 |
ejudge
judge |
|
It is enough for Petya to type the word ejudge once, and then cut off and discard the letter e. It doesn't have to print anything character-by-character, so the answer is an empty string. |
| 5 |
m
hmm |
|
It is enough to print the original word three times and the desired result will be obtained. Nothing needs to be added, so the – empty string. |