A regular expression is a sequence of characters that define a pattern of string.
In this problem, a regular expression pattern contains lowercase letters, character '*' and character '.', where:
- '.' matches any single character (for example, "a.b" matches "aab", "abb", "acb", ..., and "azb")
- '*' indicates 0 or more occurrences of the preceding character (for example, "ab*c" matches "ac", "abc", "abbc", "abbbc", and so on, that is, in this example, the preceding character b of * can occur 0 or more times)
A string and the regular expression is said to be matched if the entire string can be covered by the entire pattern.
Given a string S and a regular expression pattern P, and Q questions,
for each question, given 2 integers QS, QP,
answer if S[0, QS) matches the pattern P[0, QP).
S[0, QS) is a substring of string S from index 0 to index QS - 1, where the index starts from 0.
P[0, QP) is a substring of pattern P from index 0 to index QP - 1, where the index starts from 0.
Note that S[0, 0) is an empty string and P[0, 0) is an empty pattern.
ouo.
For #Sample Input 1:
0 0: Empty pattern matches empty string.
1 1: True since pattern "a" matches string "a".
2 3: False since the entire pattern "aaa" does not match string "aa".
4 3: False since pattern "aaa" does not match the entire string "aaaa".
For #Sample Input 2:
1 1: "a" matches "a".
1 2: "a*" matches "a", since "a*" matches 0 or many 'a'.
3 2: "a*" does not match "aab" since "a*" matches 0 or many 'a'.
For #Sample Input 3:
0 2: ".*" matches 0 of the preceding character '.' so matches emtpy string.
3 2: ".*" matches "aab" since ".*" matches 0 or many of the preceding element '.', and '.' match any single character.
3 4: ".*bc" doest not match "aab" since the last 'c' cannot match the given string.
3 5: ".*bc*" matches "aab" since "c*" matches 0 of the preceding character 'c', then pattern ".*b" matches "aab".
The first line contains a string S,
the second line contains a regular expression pattern P,
and the third line contains an integer Q, representing that there are Q questions.
In the following Q lines, each line contains 2 integers QS, QP,
representing the question is "Does S[0, QS) match the pattern P[0, QP) ?".
For all testcases:
1 <= |S|, |P| <= 500,
1 <= Q <= 250000,
0 <= QS <= |S|,
0 <= QP <= |P|.
S contains only lowercase letters.
P contains only lowercase letters, character '.' or character '*'.
For test cases 1 ~ 2: P contains no character '*'.
For test cases 3 ~ 6: 1 <= |S|, |P| <= 20.
For test cases 7 ~ 8: P contains only '.' and '*'.
For test cases 9 ~ 10: Q <= 10.
The output should contain Q lines.
For each question, output "True" if S[0, QS) matches P[0, QP) and "False" if not. (Without quotes)