Left and Right

기술이 발전해서 이제 로봇으로 우편을 배달할 수 있게 되었다. 긴 수평 도로를 따라 있는 동네에 왼쪽에서 오른쪽으로 1번부터 n번까지 번호가 붙은 n채의 집이 있다. 매일 우편 배달 로봇은 각 집에 정확히 한 통씩 편지가 들어 있는 더미를 받는다. 기계적인 제약 때문에 로봇은 편지를 정렬할 수 없다. 로봇은 항상 더미 맨 위의 편지를 확인하고, 그 편지를 받아야 하는 집을 방문해 배달한다. 로봇은 모든 편지를 배달할 때까지 이 과정을 반복한다. 그 결과 하루의 우편 배달 동안 n채의 집은 각각 로봇의 방문을 정확히 한 번씩 받는다.

우편 배달 로봇에는 배달 경로를 기록하는 추적 장치가 있다. 어느 날 장치가 고장 나서 정확한 경로를 잃어버렸다. 하지만 기술팀은 고장 난 장치에서 로봇의 이동 방향을 복구하는 데 성공했고, 이는 n − 1개의 문자로 이루어진 문자열로 나타난다. 문자열의 i번째 문자는 로봇이 방문한 (i + 1)번째 집이 i번째로 방문한 집의 왼쪽에 있으면 ‘L’, 오른쪽에 있으면 ‘R’이다. 예를 들어 n = 4이고 로봇이 2, 4, 3, 1의 순서로 집을 방문했다면 이동 방향은 “RLL”이 된다.

이동 방향이 주어지면 로봇이 집을 방문한 순서를 알아낼 수 있을지도 모른다. 기술팀은 그 일을 하는 프로그램을 작성해 달라고 요청했다. 같은 이동 방향을 만들어 내는 순서가 여러 개 있을 수 있는데, 그중에서 사전순으로 가장 앞서는 순서를 찾아야 한다.

첫째 줄에 정수 n (2 ≤ n ≤ 2 · 105)이 주어진다. 둘째 줄에 로봇의 이동 방향을 나타내는, ‘L’과 ‘R’로 이루어진 길이 n − 1의 문자열이 주어진다.

이동 방향에 따라 로봇이 집을 방문해 편지를 배달했을 수 있는 순서 중 사전순으로 가장 앞서는 순서를 한 줄에 하나씩 출력한다.