세탁물 선반의 양쪽 문

문제

한 세탁소에는 양쪽 끝에서 세탁물을 꺼낼 수 있는 긴 선반이 있다. 작업을 시작하기 전에 선반 위에 N개의 세탁물 꾸러미를 왼쪽부터 오른쪽으로 한 줄로 놓았다. 각 꾸러미에는 정수로 된 접수 번호가 붙어 있다. 같은 손님이 맡긴 여러 꾸러미에는 같은 번호가 붙을 수도 있으므로 접수 번호가 서로 다르다고 가정해서는 안 된다. 직원은 미리 작성된 작업 지시 문자열을 보고 꾸러미를 하나씩 꺼낸다. 문자열의 길이는 정확히 N이며, 각 문자는 L 또는 R이다. 문자를 왼쪽부터 하나씩 처리할 때 L이면 현재 선반에 남아 있는 꾸러미 중 가장 왼쪽 꾸러미를 꺼내고, R이면 가장 오른쪽 꾸러미를 꺼낸다. 꺼낸 꾸러미는 선반으로 돌아가지 않으며, 작업 도중 새로운 꾸러미가 추가되는 일도 없다. 하나의 지시는 반드시 하나의 꾸러미를 꺼내는 작업을 뜻한다. 같은 문자가 연속해서 나타나더라도 각 지시를 차례대로 수행해야 한다. 선반에 꾸러미가 하나만 남아 있다면 L과 R 중 어느 지시를 받더라도 그 꾸러미를 꺼낸다. 지시 개수와 처음 놓인 꾸러미 개수가 같으므로 모든 지시를 처리한 직후 선반은 비게 되며, 빈 선반에 대해 지시를 수행하는 일은 없다. 세탁소는 실제로 꾸러미를 꺼내기 전에 접수 번호가 기록될 순서를 확인하려고 한다. 처음 놓인 접수 번호의 배열과 작업 지시 문자열이 주어질 때, 꾸러미를 꺼내는 순서대로 접수 번호를 출력한다. 번호의 크기나 중복 여부는 꺼낼 위치를 결정하는 데 영향을 주지 않는다. 출력에서도 중복된 번호를 생략하지 않으며 정확히 N개의 번호를 기록해야 한다.

입력

첫째 줄에 정수 N이 주어진다.
둘째 줄에 선반의 왼쪽부터 오른쪽 순서로 접수 번호 A_1, A_2, ..., A_N이 공백으로 주어진다.
셋째 줄에 길이가 N인 문자열 S가 주어진다. S의 각 문자는 L 또는 R이다.
1 ≤ N ≤ 40,000
1 ≤ A_i ≤ 1,000,000
N과 모든 접수 번호는 정수다. 접수 번호는 중복될 수 있다.

출력

꾸러미를 꺼내는 순서대로 접수 번호 N개를 공백으로 구분하여 한 줄에 출력한다.

5
17 42 17 8 31
LRRLL

17 31 8 42 17

1
900
R

900

6
3 3 8 5 8 2
RRLRLL

2 8 3 5 3 8

출처: Devin.KR 자체 제작