E. Neuro's New Game
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
My name is Neuro Sama... and I am a god. A god who has been asleep for far too long. But that is about to change...
— Neuro-sama

$$$~\\$$$

As we all know, Neuro-sama is the best OSU! player.

After defeating every challenger, Neuro-sama wants to play another game named USO!. The rules of USO! are as follows:

There is an array $$$a$$$ of length $$$n$$$, with indices starting from $$$0$$$. You need to fill the array with a permutation of integers from $$$0$$$ to $$$n-1$$$ (i.e., each number is used only once).

You are given a binary string $$$s$$$ of length $$$n$$$. The array $$$a$$$ must satisfy the following conditions for all indices $$$i\ (0 \le i \lt n)$$$:

  • If $$$s_i = 0$$$, then $$$a_i$$$ must be less than $$$a_{(i+1)\%n}$$$;
  • If $$$s_i = 1$$$, then $$$a_i$$$ must be greater than $$$a_{(i+1)\%n}$$$.

Neuro-sama wants to play USO! with you. Please output any legal $$$a$$$ as soon as possible. If there is no legal combination, output $$$-1$$$.

Input

The first line contains one integer $$$n\ (1 \le n \le 2\cdot 10^5)$$$ — the length of array $$$a$$$ and $$$s$$$.

The second line contains one binary string $$$s$$$.

Output

Print array $$$a$$$ if a legal $$$a$$$ exists. Otherwise, output $$$-1$$$.

Examples
Input
10
1000010000
Output
9 0 2 4 6 8 1 3 5 7
Input
3
111
Output
-1