Two String Masks

Time limit2sMemory limit128 MB

Summary

Given two strings each containing one asterisk, find the shortest string obtainable by replacing the asterisks with (possibly empty) letter strings so both become equal, or report impossible.

Level: Medium5 of 10
Topics: String, Simulation, Brute force, Implementation
Solved: No attempts yet

Problem

You are given two strings S1 and S2. Each string consists of zero or more uppercase English letters and exactly one asterisk (*).

Replace each asterisk with a string made only of uppercase English letters. The replacement may also be the empty string. The two resulting strings must be identical.

Print a shortest string that can be obtained this way. If no such string exists, print -1.

Input

The first line contains S1, and the second line contains S2.

Each string has length between 1 and 50, inclusive, and consists only of zero or more uppercase English letters and exactly one asterisk (*).

Output

Print a shortest string that satisfies the condition. If no such string exists, print -1.

Examples6

Example 1
Input
```
*A
B*
```
Expected output
```
BA
```
Example 2
Input
```
HELLO*
HI*
```
Expected output
```
-1
```
Example 3
Input
```
GOOD*LUCK
*
```
Expected output
```
GOODLUCK
```

Example 4

Input

*SAMPLETEST
FOURTHSAMPLE*

Expected output

FOURTHSAMPLETEST

Example 5
Input
```
*
A*
```
Expected output
```
A
```
Example 6
Input
```
LASTCASE*
*LASTCASE
```
Expected output
```
LASTCASE
```