题目描述

编号为 $1$ 到 $N$ 的 $N$ 个人排成一列。对于每个整数 $i$（$1 \le i \le N$），第 $i$ 个人站在从左向右数第 $i$ 个位置，并持有一张卡片 $A_i$。每张卡片均为剪刀（S）、石头（R）、布（P）中的一种。

如果两个不同的人之间没有其他人，则称这两个人相邻。你可以选择相邻的两个人，让他们进行对决。每次对决按照以下方式进行：

• 如果两个人持有的卡片不同，则按照剪刀石头布的规则决定胜者。具体而言，石头（R）战胜剪刀（S），剪刀（S）战胜布（P），布（P）战胜石头（R）。
• 如果两个人持有的卡片相同，则可以由你任意指定其中一人为胜者。

败者将离场，胜者则保留自己原有的卡片，并留在原来的位置上。有人离场后，可能会有原本不相邻的两个人变得相邻，而他们之后也可以进行对决。

你需要恰好进行 $N-1$ 次对决，使得最后只剩下一名获胜者。请编写一个程序，对每个人分别判断是否存在一种安排对决的方式，使其能够成为最终获胜者。

输入格式

第一行输入一个整数 $N$。

第二行输入一个长度为 $N$ 的字符串 $A$。$A$ 的第 $i$ 个字符 $A_i$ 表示第 $i$ 个人持有的卡片，为大写英文字母 S、R、P 中的一个（$1 \le i \le N$）。

输出格式

第一行输出一个长度为 $N$ 的字符串。其中，第 $i$ 个字符应满足：如果第 $i$ 个人能够成为最终获胜者，则该字符为 $1$；否则，该字符为 $0$（$1 \le i \le N$）。

3
RPP

011

3
RPS

101

提示

样例说明 1

如果先让第 $2$ 个人和第 $3$ 个人进行对决，由于两人持有的卡片相同，因此可以由你任意指定胜者。如果指定第 $2$ 个人获胜，那么剩下的第 $1$ 个人和第 $2$ 个人将进行对决。由于布（P）战胜石头（R），因此第 $2$ 个人可以成为最终获胜者。

也可以让第 $2$ 个人和第 $3$ 个人进行对决，并指定第 $3$ 个人获胜，之后再让第 $3$ 个人与第 $1$ 个人进行对决。这样，第 $3$ 个人可以成为最终获胜者。

由于石头（R）无法战胜布（P），因此第 $1$ 个人绝不可能成为最终获胜者。

样例说明 2

如果先让第 $2$ 个人和第 $3$ 个人进行对决，由于剪刀（S）战胜布（P），因此第 $3$ 个人获胜。剩下的第 $1$ 个人和第 $3$ 个人进行对决时，由于石头（R）战胜剪刀（S），因此第 $1$ 个人可以成为最终获胜者。

如果先让第 $1$ 个人和第 $2$ 个人进行对决，由于布（P）战胜石头（R），因此第 $2$ 个人获胜。剩下的第 $2$ 个人和第 $3$ 个人进行对决时，由于剪刀（S）战胜布（P），因此第 $3$ 个人可以成为最终获胜者。 第 $2$ 个人绝不可能成为最终获胜者。

限制条件

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

$A$ 是一个长度为 $N$ 的字符串，且仅由大写英文字母 S、R、P 组成。

子任务

1. （$13$ 分）$N \le 3$。
2. （$16$ 分）字符串 $A$ 中至多包含两种不同的字符。
3. （$47$ 分）$N \le 100$。
4. （$31$ 分）$N \le 5\,000$。
5. （$43$ 分）无附加限制。

翻译由 ChatGPT-5.6 完成