Background

Wildcards are keyboard characters used when we do not know the actual characters or do not want to type the full name. Wildcards include question mark (?) and asterisk () among others, where "?" can replace one character and "" can replace zero or more characters.

A new wildcard "@" is now defined, which, in a string, replaces a fixed number of characters.

Problem Description

When using "@", users naturally prefer to input as few "@" as possible. Given a string with wildcards "?" and "" and an original string, the task is to first determine if the wildcard string matches the original string. If they match, find the minimum number of wildcard "@" needed to replace the "?" and "" in the wildcard string while ensuring the modified wildcard string still matches the original string.

Input Format

The first line of the input file is a string describing the wildcard string.

The second line is also a string describing the original string.

Output Format

The first line of the output file is a string. If the wildcard string matches the original string, output "matched" and on the next line output an integer describing the minimum number of wildcard "@" required. If they do not match, output "not matched".

Sample Input and Output

Sample Input #1

1*456??
111111145678

Sample Output #1

matched
4

Sample Input #2

1*456
1111111452

Sample Output #2

not matched

Notes

Sample Explanation 1

The two strings clearly match. The wildcard string 1*456?? can be replaced with 1@@@456@, requiring a minimum of 4 "@", where each "@" replaces two characters. It can be proven that this is the optimal case.

The wildcard string 1*456?? can also be replaced with 1@@@@@@456@@, where each "@" replaces one character, requiring 8 "@", which is not as optimal as the previous case.

Sample Explanation 2

The two strings do not match.

Data Range

For 100% of the data, the lengths of the strings are both less than 3000.

The original string contains only letters and digits, and the wildcard string contains only letters, digits, and the wildcards "?" and "*". The matching method is guaranteed to be unique.

见题面 Input 部分

见题面 Output 部分