Digit Patterns

We construct R-expression in the following way:

1. 0, 1, 2, ..., 9 and 0*, 1*, ..., 9* are R-expressions
2. if A and B are R-expressions, so do (A), A + B, AB and (A)∗. • (union) A + B matches all the strings s such that either A or B (or both) matches s. • (concatenation) AB matches all the strings in the form s1s2 (the concatenation of s1 and s2), where A matches s1 and B matches s2. • (closure) (A)∗ matches all the strings in the form s1s2s3 . . . sk (k ≥ 0), where A matches every si. (Note s1, s2, ... don’t have to be equal to each other) R-expressions can only be constructed by rule 1 and 2. In this problem, an R-expressions will not match the empty string. Note that “concatenation” has higher priority than “or”, so 11+22 is interpreted as (11)+(22), not 1(1+2)2. Given a text T, you’re to find all position “matching point” p, such that R matches a substring of T, ending at position p (positions start from 1). For example, if R = ‘1(2+3)4’, T = ‘012345’, there is exactly one matching point 5, because T matches 1234, which is ending at position 5. Input There are at most 40 test cases. Each test case begins with an integer n (1 ≤ n ≤ 10) and an R-expressions (length not exceeding 500). The next line contains the text (length not exceeding 107). Both the R-expression and the text only uses the first n digits (i.e., 0, 1, ..., n − 1). It is guaranteed that the R-expression will not match the empty string. The size of input does not exceed 20MB. Output For each test case, output a single line containing the matching points, in ascending order, in one line. It is guaranteed that there is at least one matching point for each test case. Sample Input Hint This problem is hard. You need to know some theory behind regular expressions, not just how to use them. Please make sure your program can pass the test cases in the gift package in the contest website. 6 1(2+3)4 012345 2 00(10+100) 00100 Sample Output 5 1245