Description

The HURRICANE team has recently received a task to search for text, specifically to match substrings that satisfy specified conditions within a long text composed of digits. The search conditions are described using regular expressions such as (0+10*1)*10*. The inductive definition of these regular expressions is as follows:

1. $0, 1, \dots, 9, 0^*, 1^*, \dots, 9^*$ are regular expressions;
2. If $A$ and $B$ are regular expressions, then $(A)$, $A+B$, $AB$, and $(A)^*$ are regular expressions;
3. Only expressions constructed according to the above methods are regular expressions.

Here, $A+B$ denotes an "OR" relationship, $AB$ denotes a "concatenation" relationship, and $(A)^*$ denotes that the content of $A$ is "repeated" zero or more times. For example, the regular expression $(12+3)(4+5)6^*$ can match strings starting with either $124, 125, 34,$ or $35$, followed by zero or more $6$s (e.g., the string $12566$). The regular expression $(1+0)^*$ can match all strings composed of $0$ and $1$, or an empty string. If a regular expression cannot match an empty string, it is called non-empty. This problem considers only non-empty regular expressions.

If there exists a substring ending at a certain position in the given text that can be matched by the given non-empty regular expression, then that position is said to be matchable. The task for the HURRICANE team is to find all matchable positions. Can you help them complete this task?

Input

The input consists of a regular expression as defined above and a long string of text:

• The first line contains the regular expression, which consists of two parts separated by a space:
  • A non-negative integer $n$ ($1 \le n \le 10$), representing that the set of digits we are considering (i.e., the digits appearing in the regular expression and the text) is $0, 1, \dots, n-1$.
  • A regular expression, which is composed of the 4 symbols $\{'(', ')', '+', '*'\}$ and the digits $\{0, \dots, n-1\}$. The length of the expression does not exceed $500$ characters.
• The second line is a string composed of digits from $0$ to $n-1$, which is the text to be processed. The length of this text does not exceed $10,000,000$ characters.

Output

The output file contains a single line consisting of integers separated by spaces, representing all matchable positions in the text, listed in ascending order.

Examples

Input 1

4 12333+33 
312331

Output 1

5

Note

For the input example, the text to be processed is '312331', where only the position of the 5th character (the last '1') is matchable. In this case, the '33' in the regular expression '12333+33' can match it.

Subtasks

There are ten test cases in total, each worth 10% of the total score. For each test case, if your answer is correct, you will receive the full points for that test case; otherwise, you will receive 0 points.

Hint: In the test data for this problem, there are 6 test cases where the regular expression does not contain '*', among which 3 test cases contain regular expressions composed only of digits and '+'. One test case has a text length not exceeding 1,000,000 characters. This problem has strict time limits, so please optimize your algorithm as much as possible.