Real Information - 1

• In Progress Hard

Helpful

A company wants to send an important information to its clients, but they also want to keep it a secret. So they send two messages to clients, the first message contains the real_information, but mixed with fake information. The second_message contains only the real_information that is in first_message, but few characters in second_message are encrypted with special characters # and $. The second message contains only one or zero $.

The company also provided below instructions to the clients:

The real information is always at the beginning of the first message

The real information in second_message is encypted in such a way that # represents any letter and $ represents the zero or more repetitions of previous letter of $ in second_message

Now, the clients need to match the characters in second_message with the first message and extract the real information contained in first_message

For example, if the first message is assignment and second_message is asS#gn, $ and # in second message matches with s and i respectively. So, the real_information is assign.
Your task is to help clients find the real_information that is sent by the company.

Given first message and second_message, write a program to print the real_information by matching the characters in second_message with the first message by following the instructions. If there are multiple possible values of real_information, then print the one with the largest length.

Note

If the previous character of $ in second_message is #, $ matche any zero or more letters in first message

Example: If first message is combination and second_message is co#$t # matches with m and $ matches with bina as $ represents zero or more repetitions of #. As # represents any letter, $ matches all the characters till

If there are multiple possible values of real information, then print the one with the largest length.

Example: if first message is construction and second_message is co#St # matches with n and S matches with s and struc. The real_information would be const or construct. Then, the real_information is construct as it has larger length than const.
Input

The first line of input contains a string representing first_message

The second line of input contains a string representing second_message

Output

The output should be a single line containing a string representing the real_information

Constraints

A maximum of one $ will be given in the second_message which contains the encrypted real_information

Explanation

For example, if the given first message = "hellloclient and second_message = "h#l$o"

hin second_message matches with h in first_message

#in second_message matches with e in first message as ## represents any letter.

I in second message matches with I in first_message
$ in second_message matches with Il in first_message as $ represents represents zero or more repetitions of previous character of $, that is I. So, it matches the I characters that are in first message till o, that is II.

o in second_message matches with o in first_message
So, the real information is helllo.

The output should be helllo.


Sample Input 1

hellloclient

h#1$o

Sample Output 1

helllo

Sample Input 2

helloclient he#$i

Sample Output 2

hellocli

Sample Input 3

clientiseverythingisok

C#$1

Sample Output 3

clientiseverythingi

give me the efficient python code for this