Problem Description

I love sushi.

By the way, the integer $X$ is in base $a$ with $n$ digits. The most significant digit can be $0$.
Also, $F(X)$ is the sum of the digits of $X$ in base $a$ expressed in decimal. For example, if $a = 7$ and $X = 562$, then $F(X) = 13$.

Now, please output $K$ integers $X$ that satisfy all of the following three conditions, in ascending order.

• $F(X) = m$.
• $X' \mod p = t$ (where $X'$ is the integer $X$ converted to decimal).
• For all integers $i$ ($1 \leq i \leq n$) where $s_i =$ 0, the digit in the $a^{n-i}$ place of the integer $X$ must be $0$.
• For example, if $n = 7$, $a = 10$, and $s =$ 1110110, then the digits in the $1000$ place and $1$ place of $X$ must be $0$.

If there are fewer than $K$ such integers, output all integers that satisfy the conditions in ascending order, followed by -1.

For detailed output format, please refer to the "Output Format" section.

Input Format

The input is given from the standard input in the following format:

$n$ $a$ $m$ $p$ $t$ $K$ $s_1$ $s_2$ $s_3$ $s_4$...$s_n$

Output Format

If there are $K$ or more integers that satisfy the conditions, output them in the following format:

(Information of the 1st smallest integer) (Information of the 2nd smallest integer) (Information of the 3rd smallest integer) : (Information of the $K$th smallest integer)

If there are fewer than $K$ integers that satisfy the conditions, output them in the following format (where $K'$ is the number of integers that satisfy the conditions):

(Information of the 1st smallest integer) (Information of the 2nd smallest integer) (Information of the 3rd smallest integer) : (Information of the $K'$th smallest integer) -1

When the integer to be output is represented as $g_{n-1}a^{n-1}+g_{n-2}a^{n-2}+...+g_0a^0$ ($0 \leq g_i \leq a-1$), output it in one line in the following format:

$g_{n-1}$ $g_{n-2}$ $g_{n-3}$ ... $g_{0}$

Sample Input and Output

Sample Input #1

3 10 1 5 0 2
111

Sample Output #1

0 1 0
1 0 0

Sample Input #2

6 10 26 241 74 25
111110

Sample Output #2

0 6 6 5 9 0
0 8 8 2 8 0
1 0 9 9 7 0
1 9 6 7 3 0
2 8 3 4 9 0
3 2 6 8 7 0
3 4 8 5 6 0
3 9 1 9 4 0
4 7 8 7 0 0
5 4 3 7 7 0
5 6 5 4 6 0
5 8 7 1 5 0
6 0 8 8 4 0
6 7 3 9 1 0
6 9 5 6 0 0
7 1 7 2 9 0
7 6 0 6 7 0
7 8 2 3 6 0
8 2 5 7 4 0
8 4 7 4 3 0
8 6 9 1 2 0
8 9 0 8 1 0
9 3 4 1 9 0
-1

Sample Input #3

3 2 3 7 0 2000
111

Sample Output #3

1 1 1
-1

Sample Input #4

40 23 166 240 130 1117
1000000000100000000010000000001000000000

Sample Output #4

-1

Notes/Hints

Constraints

• $1 \leq n \leq 100$.
• $2 \leq a \leq 1,000,000$.
• $0 \leq m \leq 600$.
• $2 \leq p \leq 600$.
• $0 \leq t$.
• $1 \leq K \leq 2,000$.
• $s_i$ is either 0 or 1.
• $n$, $a$, $m$, $p$, $t$, and $K$ are integers expressed in decimal.

Partial Points

This problem is divided into several sub-tasks. A sub-task is considered solved if all test cases in that sub-task are solved correctly.
The score for a submission is the sum of the points for the solved sub-tasks.

1. (7 points) $m = 1$.
2. (8 points) $n \leq 6$, $a \leq 10$.
3. (24 points) $n \leq 32$, $a = 2$.
4. (29 points) $n \leq 50$, $a \leq 10$, $m \leq 50$, $p \leq 50$.
5. (23 points) $a \geq m$.
6. (9 points) No additional constraints.

Sample Explanation 1

The integers that satisfy the conditions are only $10$ and $100$. Although $10$ is a 2-digit number, since the most significant digit can be $0$, it can be considered as $010$ and satisfies the conditions. Note that this input example satisfies the constraints of sub-task 1.

Sample Explanation 2

In this input example, there are only 23 integers that satisfy the conditions. Since $K = 25$, outputting -1 on the last line will result in a correct answer.

Sample Explanation 4

There may be cases where no integers satisfy the conditions.

见题面 Input 部分

见题面 Output 部分