Shortest Matching String with Substring Constraint

Given a simplified regular expression E and a substring S, your task is to find the shortest string that matches the regular expression E and contains S as a substring.

The regular expression E is defined as follows:

• An empty string ("") is a regular expression that only matches the empty string.
• A single lowercase letter c is a regular expression that matches the string consisting of the single letter c.
• A dot . is a regular expression that matches any single letter.
• Alternation: If α and β are regular expressions, then (α|β) is a regular expression that matches a string s if and only if s matches either α or β.
• Concatenation: If α and β are regular expressions, then (αβ) is a regular expression that matches a string s if and only if s can be split as xy where x matches α and y matches β.
• Kleene star: If α is a regular expression, then (α*) is a regular expression that matches a string s if and only if s is empty or s can be decomposed into one or more substrings, each of which matches α.

Parentheses can be omitted. The operator precedence is: Kleene star has highest priority, concatenation has medium priority, and alternation has lowest priority. For example, the expression abc*|de is parsed as (ab(c*))|(de).

For instance, the string abcabcab matches the regular expression a(bc|a)*ab, while abcbab does not.

Input: Two lines. The first line contains the regular expression E and the second line contains the substring S.

Output: Print the shortest string that matches E and contains S as a substring. If no such string exists, output Impossible.

inputFormat

The input consists of two lines:

1. The first line is a string E representing a simplified regular expression.
2. The second line is a string S representing the substring that must appear in the output.

Both E and S contain only lowercase letters and symbols from the regular expression grammar (., |, *, and parentheses). Note that the empty string is represented as an empty input.

outputFormat

Output a single line containing the shortest string that both matches the regular expression E and contains S as a substring. If no such string exists, output Impossible.

sample

a(bc|a)*ab
abc

abcab