Module: Greatest common subsequence


Problem

5 /5


Template with? *

Problem

A pattern is a string consisting of English letters (a, ..., z, A, ..., Z) and symbols ? And *. Each of the characters ? it is allowed to replace with one arbitrary letter, and each of the symbols * – to an arbitrary (possibly empty) sequence of letters. Any string of letters that can be obtained from a template by such substitutions will be said to satisfy this template.
 
There are two templates. It is required to find a string of minimum length that satisfies both patterns, or to display a message that such a string does not exist.
 
Input
The given patterns are written in the first two lines of the input. The length of each template does not exceed 80 characters.

Output
Print a minimum length string that satisfies both patterns, or the message "No solution!"

Enter Output
AB?
*BC
ABC