\(1\)번부터 \(N\)번까지 번호가 부여된 \(N\)명의 사람이 일렬로 서 있다. \(i\) (\(1 \le i \le N\))번 사람은 왼쪽에서 \(i\)번째에 서 있으며, 하나의 카드 \(A_i\)를 가지고 있다. 각 카드는 가위(S), 바위(R), 보(P) 중 하나이다.

서로 다른 두 사람 사이에 다른 사람이 없다면, 그 두 사람은 서로 인접하다고 하자. 여러분은 인접한 두 사람을 골라 대결시킬 수 있다. 한 번의 대결은 다음과 같이 진행된다.

• 두 사람의 카드가 서로 다르면, 가위바위보 규칙에 따라 승자가 결정된다. 즉, 바위(R)는 가위(S)를 이기고, 가위(S)는 보(P)를 이기고, 보(P)는 바위(R)를 이긴다.
• 두 사람의 카드가 같으면, 여러분이 승자를 임의로 정할 수 있다.

패자는 퇴장하며, 승자는 자신의 카드를 그대로 유지한 채 그 자리에 남는다. 퇴장으로 인해 새롭게 인접해지는 두 사람이 생길 수 있으며, 두 사람은 이후 대결을 할 수 있다.

여러분은 정확히 \(N - 1\)번의 대결을 진행하여 단 한 명의 우승자만 남기려 한다. 각 사람에 대해, 그 사람이 우승자가 될 수 있도록 대결하는 방법이 존재하는지 판별하는 프로그램을 작성하라.

• \(1 \le N \le 200\,000\)

• \(A\)는 영어 알파벳 대문자 S, R, P로만 이루어진 길이 \(N\)의 문자열이다.

첫 줄에 정수 \(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\)).

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2026 > 1차 대회 > 초등부 2번