409394: GYM103496 G Galge Gamer Guy

Bob is excited to play the brand new video game Funny Girls (Kakatawa Shoujo) that Alice had gotten him as a gift! It's a visual novel with dating sim elements. It belongs to a genre of games whose main gameplay involves choosing one of several bachelorettes to romantically pursue, so the genre is sometimes referred to as galge (a shortening of "gal game").

Bob has really been enjoying this game, and discusses it with Alice every night. Alice mentioned that her favorite character is Alexa, the shy student council president who pines hopelessly for the main character but is unable to tell him how she feels. Bob, however, is much more interested in Cecille, the fun extroverted athletic girl with a carefree attitude. He thinks Alexa is nice, but finds Cecille to be a much more likeable and compelling character. Weirdly enough, when he mentioned this to Alice, she suddenly stopped responding to his messages...

Bob has almost finished the game, and could possibly end up with Alexa or Cecille, depending on whomever he meets next. The map of the game consists of $$$n$$$ locations arranged in a row, labeled $$$1$$$ to $$$n$$$ from left to right. In one step, he can travel from his current location to any of the locations directly adjacent to it. The level begins in a random location.

Some of these locations have an event flag. If he is in a location with Alexa's event flag, he ends up with Alexa and the game immediately ends. If he is in a location with Cecille's event flag, he ends up with Cecille and the game immediately ends. Note that if Bob already begins a level in a location with an event flag, then the game immediately ends without him having to move.

Not only will Bob's starting location in the final chapter be randomized, but he also is undecided as to whether he wants to end up with Alexa or Cecille. Thankfully, the event flags are fixed and always appear in the same locations. Thus, for each girl and for each possible starting position, help Bob find the minimum number of steps that he needs to travel in order for him to end the game with that girl.

The first line of input contains a single integer $$$n$$$, the number of locations.

The second line of input contains a string with $$$n$$$ characters. The $$$i$$$th character is A if the $$$i$$$th location has Alexa's event flag, is C if it has Cecille's event flag, and is . if it has neither's event flag.

First, output a line containing $$$n$$$ space-separated integers, the $$$k$$$th of which is the minimum number of steps to any of Alexa's event flags, from starting location $$$k$$$.

Then, output another line containing $$$n$$$ space-separated integers, the $$$k$$$th of which is this time the minimum number of steps to any of Cecille's event flags, from starting location $$$k$$$.

Whenever it would be impossible to end up with that girl from some $$$k$$$, output $$$-1$$$ as the answer to that starting location.

Note: Because of the possibly large output, it is recommended that Python users submit to PyPy.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 2\times 10^5 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & n \leq 800 \\ \hline 2 & \mathbf{15} & \text{There is at most one event flag overall.} \\ \hline 3 & \mathbf{15} & \text{Alexa has at most one event flag.} \\ & & \text{Cecille has at most one event flag.} \\ \hline 4 & \mathbf{20} & \text{All event flags belong to the same girl.} \\ \hline 5 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

4
.A..

1 0 1 2
-1 -1 -1 -1

5
C..CA

-1 -1 -1 -1 0
0 1 1 0 -1

6
CA...C

-1 0 1 2 3 -1
0 -1 3 2 1 0

In the third sample input, suppose that Bob starts at location $$$3$$$ and wants to end the game will Cecille. Note that he has to move $$$3$$$ steps to the right to reach the C at location $$$6$$$. He cannot move $$$2$$$ steps to the left to reach the C at location $$$1$$$, because then he would have to pass through the A at location $$$2$$$ first, which would already immediately end the game with Alexa.