Problem Description

There are $N$ people numbered from $1$ to $N$ standing in a line. For each integer $i$ ($1 \le i \le N$), person $i$ stands at the $i$-th position from left to right and holds a card $A_i$. Each card is one of Scissors (S), Rock (R), or Paper (P).

Two different people are called adjacent if there is no one between them. You may choose two adjacent people and let them play a duel. Each duel is carried out as follows:

• If the two people hold different cards, the winner is determined by the rules of rock-paper-scissors. Specifically, Rock (R) beats Scissors (S), Scissors (S) beats Paper (P), and Paper (P) beats Rock (R).
• If the two people hold the same card, you may choose either one to be the winner.

The loser leaves the line. The winner keeps their original card and stays at their original position. After someone leaves, two people who were not adjacent may become adjacent, and they can duel later.

You must perform exactly $N-1$ duels so that only one winner remains in the end. Write a program to determine, for each person, whether there exists an arrangement of duels that allows them to become the final winner.

Input Format

The first line contains an integer $N$.

The second line contains a string $A$ of length $N$. The $i$-th character $A_i$ of $A$ indicates the card held by person $i$, and is one of the uppercase letters S, R, P ($1 \le i \le N$).

Output Format

Output a string of length $N$ on the first line. For each $i$, the $i$-th character should be: $1$ if person $i$ can become the final winner; otherwise $0$ ($1 \le i \le N$).

3
RPP

011

3
RPS

101

Hint

Sample Explanation 1

If person $2$ duels person $3$ first, since they hold the same card, you may choose the winner. If you choose person $2$ to win, then the remaining person $1$ and person $2$ will duel. Since Paper (P) beats Rock (R), person $2$ can become the final winner.

You can also let person $2$ duel person $3$ and choose person $3$ to win, then let person $3$ duel person $1$. In this way, person $3$ can become the final winner.

Since Rock (R) cannot beat Paper (P), person $1$ can never become the final winner.

Sample Explanation 2

If person $2$ duels person $3$ first, since Scissors (S) beats Paper (P), person $3$ wins. When the remaining person $1$ duels person $3$, since Rock (R) beats Scissors (S), person $1$ can become the final winner.

If person $1$ duels person $2$ first, since Paper (P) beats Rock (R), person $2$ wins. When the remaining person $2$ duels person $3$, since Scissors (S) beats Paper (P), person $3$ can become the final winner. Person $2$ can never become the final winner.

Constraints

$1 \le N \le 200\,000$.

$A$ is a string of length $N$ and consists only of the uppercase letters S, R, P.

Subtasks

1. (13 points) $N \le 3$.
2. (16 points) The string $A$ contains at most two different characters.
3. (47 points) $N \le 100$.
4. (31 points) $N \le 5\,000$.
5. (43 points) No additional constraints.

Translated by ChatGPT-5.6.

Translated by ChatGPT 5