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의 문자열이다.

부분문제

1. (13점) \(N \le 3\)
2. (16점) 문자열 \(A\)는 최대 두 종류의 문자로만 이루어져 있다.
3. (47점) \(N \le 100\)
4. (31점) \(N \le 5\,000\)
5. (43점) 추가 제약 조건 없음.