Problem Description

A certain checking system needs to use each of the numbers $1, 2, \dots, n$ exactly once and arrange them into a sequence of length $n$, $p_1, p_2, \dots, p_n$. Such a sequence is called a permutation.

The system generates a check string of length $n-1$ based on the parity of the absolute differences between adjacent numbers in the permutation. For each $1 \le i < n$, the $i$-th check character $c_i$ is determined by the following rules:

• If $|p_i - p_{i+1}|$ is even, then $c_i$ is $0$.
• If $|p_i - p_{i+1}|$ is odd, then $c_i$ is $1$.

Now you are given a target check string $S$ of length $n-1$. You need to construct a permutation such that the generated check string $c_1 c_2 \dots c_{n-1}$ is exactly equal to $S$.

If there are multiple valid permutations, output the lexicographically smallest one. For two different permutations $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$, if there exists a position $k$ such that the first $k-1$ numbers are the same and $a_k < b_k$, then permutation $a$ is lexicographically smaller than permutation $b$.

If no such permutation exists, output $-1$.

Input Format

The first line contains an integer $n$, representing the number of labels.

The second line contains a string $S$ of length $n-1$, representing the target check string. The string consists only of characters $0$ and $1$.

Output Format

If no valid permutation exists, output a single integer $-1$ on one line.

Otherwise, output $n$ integers on one line, representing the lexicographically smallest valid permutation. Adjacent integers should be separated by one space.

5
1010

1 2 4 3 5

6
00000

-1

8
0101101

1 3 2 4 5 6 8 7

Hint

Sample Explanation 1

The adjacent differences of this permutation are, in order:

• $|1-2|=1$, which is odd, corresponding to $1$.
• $|2-4|=2$, which is even, corresponding to $0$.
• $|4-3|=1$, which is odd, corresponding to $1$.
• $|3-5|=2$, which is even, corresponding to $0$.

Therefore, the generated check string is $1010$. Among all valid permutations, $1 \ 2 \ 4 \ 3 \ 5$ is lexicographically the smallest.

Sample Explanation 2

Every character of the target check string is $0$, so every adjacent difference must be even, meaning the two numbers must have the same parity. Then all numbers in all positions must have the same parity, but among $1$ to $6$ there are both odd and even numbers, so there is no solution.

Sample Explanation 3

The check string generated by the output permutation is, in order, $0$, $1$, $0$, $1$, $1$, $0$, $1$, which is the same as the target check string $0101101$.

Constraints and Notes for Testdata

For $30\%$ of the testdata, $2 \le n \le 8$.

For $60\%$ of the testdata, $2 \le n \le 5000$.

For all testdata, $2 \le n \le 2 \times 10^5$, and the length of $S$ is $n-1$.

Translated by ChatGPT 5