提示: 欢迎访问OurACM平台。
Problem 1381 Regular Expressions

Accept: 62    Submit: 174
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

You are given two regular expressions R1 and R2 and should find minimal string S matching both. String consists of capital latin letters A..Z. Regular expression is word consisting of A..Z and *,? symbols. The symbol "*" corresponds to any word or empty word. The symbol "?" corresponds to one letter.

Input

There are several test cases in the input. Each case contains two lines, indicate the regular expressions R1 and R2 respectively. Each line has less than 1000 characters.

Process to the end of file.

Output

For each case, output the minimal length of the string matching both regular expressions. If string matching R1 and R2 does not exist, then output "No Solution!".

Sample Input

?*A*? ??? B*A*A ?B?

Sample Output

3 No Solution!

Source

FZU 2005

Submit  Back  Status  Discuss