Problem Description

Given a string $ S $ of length $ N $ consisting only of 0 and 1, find a sequence $P=(P_1,P_2,\dots,P_N)$ of length $ N $ that satisfies all of the following conditions. If no such sequence exists, output -1.

• The sequence $ P $ is a permutation of $(1,2,\dots,N)$, i.e., $ P $ is a rearrangement of $(1,2,\dots,N)$.
• For all $1 \le i \le N$, the following conditions must be satisfied:
• If the $ i $-th character of $ S $ is 1, then $ P_i = i $.
• If the $ i $-th character of $ S $ is 0, then $P_i \neq i$.

Input Format

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

$ N $ $ S $

Output Format

If no sequence $ P $ satisfies the conditions, output -1.
If such a sequence exists, output each element of the sequence $ P $ as an integer separated by spaces.

Sample Input and Output

Sample Input #1

5
10101

Sample Output #1

1 4 3 2 5

Sample Input #2

4
1110

Sample Output #2

-1

Sample Input #3

12
001110110010

Sample Output #3

12 6 3 4 5 1 7 8 2 9 11 10

Notes/Hints

Constraints

• $1 \le N \le 10^5$
• $ S $ consists only of 0 and 1.

Sample Explanation 1

Since the 1st, 3rd, and 5th characters of $ S $ are 1, it is necessary that $ P_1 = 1, P_3 = 3, P_5 = 5 $. Since the 2nd and 4th characters of $ S $ are 0, it is necessary that $P_2 \neq 2, P_4 \neq 4$. For this input, the only sequence $ P $ that satisfies the conditions is $ (1, 4, 3, 2, 5) $.

Sample Explanation 2

If no sequence $ P $ satisfies the conditions, output -1.

Sample Explanation 3

The following output is also considered correct:

2 1 3 4 5 9 7 8 10 12 11 6

见题面 Input 部分

见题面 Output 部分