Wildcard Pattern Matching

You are given two strings: a text string s (consisting of lowercase letters) and a pattern string p (consisting of lowercase letters, '?' and '*'). The pattern string p may contain the wildcard characters:

• '*' which matches any sequence of characters (including the empty sequence), and
• '?' which matches any single character.

Your task is to determine whether the text string s matches the pattern p in its entirety.

The problem can be formulated using dynamic programming. Let (dp[i][j]) be true if the first (i) characters of s match the first (j) characters of p. The recurrence relations are as follows:

[ \begin{aligned} dp[0][0] &= true,\ dp[0][j] &= dp[0][j-1] \quad \text{if } p[j-1] = '' \[6pt] dp[i][j] &= \begin{cases} dp[i][j-1] \text{ or } dp[i-1][j] & \text{if } p[j-1] = '',\[6pt] dp[i-1][j-1] & \text{if } p[j-1] = '?' or s[i-1] = p[j-1],\[6pt] false & \text{otherwise.} \end{cases} \end{aligned} ]

Your program should read input from stdin and print the result (either "True" or "False") to stdout.

inputFormat

The input consists of two lines. The first line contains the string s (only lowercase letters). The second line contains the pattern string p (lowercase letters, '*' and '?').

outputFormat

Output a single line containing either "True" if the string s matches the pattern p, or "False" otherwise.## sample

aa
a

False