All submissions for this problem are available.
Chef loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
Chef likes sequences of n positive integers, each of which does not exceed m. The total number of such sequences is equal to m^n.
Chef has an array C of n-1 integers. Let F(x) be equal to the number of lucky digits in decimal representation of integer x. Let there be a sequence A of n integers (1-based numeration). Chef calls it lucky when the following hold: if for each i (1 <= i < n) if C[i] equals to 1, then F(A[i]) must be equal to F(A[i+1]) and if C[i] equals to 0, then F(A[i]) must not be equal to F(A[i+1]).
Chef has integers n, m, k and an array C. He wants to find out the k-th lucky sequence for a given array C. Help him. If the k-th lucky sequence does not exist, print the only integer -1.
The k-th lucky sequence is the k-th (1-based numeration) sequence in lexicographically sorted list of all lucky sequences for given integers n, m and an array C. The sequence A is lexicographic less than the sequence B if there exits integer x (1 <= x <= n) that A[x] < B[x] and A[y] = B[y] for all y (1 <= y < x).
First line contains one number T - the number of test cases. Each test is formed as following: first line contains 3 integers n, m, and k. Next line contains n-1 integers - array C for corresponding test.
For each T test cases print sequence of integers - answer for corresponding test.
2 <= T <= 10
2 <= n <= 50
1 <= m, k <= 10^9
0 <= C[i] <= 1
Input: 2 2 4 7 0 3 7 4 0 1 Output: -1 1 7 7
|Tags||april12, medium, witua|
|Time Limit:||0.168831 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.