Deranged Cycle Construction

You are given an integer n and a binary string S of length n (each character is either 0 or 1), and a nonnegative integer l.

We wish to construct a permutation p of the set {1,2,…,n} satisfying the following conditions:

• For every i (1 ≤ i ≤ n), p[i] ≠ i (i.e. p is a derangement).
• For every index i such that S[i] = 1, if we define the function $$ f_{p,k}(i)=\begin{cases} i & k=0\\ f_{p,k-1}(p[i]) & k\neq 0 \end{cases} $$ then it must hold that $$ f_{p,l}(i)= i. $$ (For indices where S[i] = 0 there is no additional restriction.)

Recall that applying the permutation p repeatedly, the value fp,l(i) = pl(i) is the element reached after following the cycle l times starting from i. For an element i in a cycle of length c, we have fp,l(i) = i if and only if l mod c = 0.

Note: A permutation of {1,2,…,n} is an arrangement in which each integer between 1 and n appears exactly once. In our construction, every cycle must have length at least 2 (due to the derangement condition).

If no such permutation exists, output -1.

inputFormat

The first line of input contains an integer n (the length of the string and the size of the permutation).
The second line contains the binary string S of length n.
The third line contains the nonnegative integer l.

outputFormat

If a valid permutation exists, output n space‐separated integers representing the permutation p. Otherwise, output -1.

sample

5
01010
0

2 3 4 5 1