问题描述

某个校验系统需要把 $1, 2, ..., n$ 这 $n$ 个编号各使用一次，排成一个长度为 $n$ 的序列 $p_1, p_2, ..., p_n$。这样的序列称为一个排列。

系统会根据排列中相邻两个编号的差值奇偶性生成一个长度为 $n - 1$ 的校验串。对于每个 $1 ≤ i < n$，第 $i$ 位校验字符 $c_i$ 按如下规则确定：

• 如果 $|p_i − p_{i+1}|$ 为偶数，则 $c_i$ 为 $0$；
• 如果 $|p_i − p_{i+1}|$ 为奇数，则 $c_i$ 为 $1$。

现在给定一个长度为 $n - 1$ 的目标校验串 $S$。你需要构造一个排列，使它生成的校验串 $c_1c_2 ...c_{n−1}$ 恰好等于 $S$。

如果存在多个满足要求的排列，请输出字典序最小的一个。对于两个不同排列 $a_1, a_2, ..., a_n$ 与 $b_1, b_2, ..., b_n$，若存在位置 $k$，使得前 $k − 1$ 个数都相同且 $a_k < b_k$，则称排列 $a$ 的字典序小于排列 $b$。

如果不存在满足要求的排列，请输出 $−1$。

输入格式

第一行包含一个整数 $n$，表示编号数量。

第二行包含一个长度为 $n − 1$ 的字符串 $S$，表示目标校验串，字符串仅由字符 $0$ 和 $1$ 组成。

输出格式

如果不存在满足要求的排列，输出一行一个整数 $−1$。

否则输出一行 $n$ 个整数，表示字典序最小的合法排列。相邻两个整数之间用一个空格分隔。

测试数据

样例输入 1

5
1010

样例输出 1

1 2 4 3 5

样例说明 1

该排列对应的相邻差值依次为：

• $|1 − 2| = 1$，为奇数，对应 $1$；
• $|2 − 4| = 2$，为偶数，对应 $0$；
• $|4 − 3| = 1$，为奇数，对应 $1$；
• $|3 − 5| = 2$，为偶数，对应 $0$。

因此生成的校验串为 $1010$。在所有合法排列中，$1 2 4 3 5$ 的字典序最小。

【样例输入 2】

6
00000

【样例输出 2】

-1

【样例说明 2】

目标校验串的每一位都是 $0$，因此任意相邻两个编号的差值都必须为偶数，也就是它们奇偶性相同。这样所有位置上的编号都必须具有相同奇偶性，但 $1$ 到 $6$ 中既有奇数也有偶数，所以无解。

【样例输入 3】

8
0101101

【样例输出 3】

1 3 2 4 5 6 8 7

【样例说明 3】

输出排列生成的校验串依次为 $0、1、0、1、1、0、1$，与目标校验串 $0101101$ 相同。

数据分布

【评测用例规模与约定】

对于 $30$ 的评测用例，$2 ≤ n ≤ 8$。

对于 $60$ 的评测用例，$2 ≤ n ≤ 5000$。

对于所有评测用例，$2 ≤ n ≤ 2 × 10^5$，且 $S$ 的长度为 $n − 1$。