题目描述

给定一个长度为 $n$、仅由字符 $\texttt{a}$,$\texttt{b}$,$\texttt{c}$ 组成的字符串 $s=s_1s_2\dots s_n$。请你构造一个长度为 $n$ 的排列 $p$，使得下列三个和的奇偶性相同： $\hspace{23pt}\bullet\,$所有满足 $s_i=\texttt{a}$ 的位置 $i$ 对应的 $p_i$ 之和； $\hspace{23pt}\bullet\,$所有满足 $s_i=\texttt{b}$ 的位置 $i$ 对应的 $p_i$ 之和； $\hspace{23pt}\bullet\,$所有满足 $s_i=\texttt{c}$ 的位置 $i$ 对应的 $p_i$ 之和。 【名词解释】 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，$\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。官方中文

输入格式

第一行输入一个整数 $n\left(1\leq n\leq 2\times 10^5\right)$，表示字符串的长度。 第二行输入一个长度为 $n$ 的字符串 $s$，保证其仅由字符 $\texttt{a}$、$\texttt{b}$ 和 $\texttt{c}$ 组成。官方中文

输出格式

如果不存在满足条件的排列，请输出 $-1$；否则输出 $n$ 个整数 $p_1,p_2,\dots,p_n$，表示你所构造的排列。官方中文

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。官方中文