학원 안내 카드 돌리기

문제

한 학원은 상담 순서를 안내하기 위해 책상 위에 N장의 카드를 한 줄로 놓는다. 카드가 놓이는 자리에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 각 카드에는 안내용 정수가 하나 적혀 있다. 카드에 적힌 수가 같아도 카드는 각각 별개이며, 카드에 적힌 수는 카드를 옮기는 동안 바뀌지 않는다. 직원은 처음 카드 배치를 기록한 뒤 여러 차례 배치를 바꾼다. 배치를 바꾸는 지시는 R과 S의 두 종류다. R 지시는 현재 가장 오른쪽에 있는 카드 한 장을 꺼내 가장 왼쪽에 놓으라는 뜻이다. 이때 원래 1번부터 N-1번 자리에 있던 카드는 각각 한 자리씩 오른쪽으로 이동한다. 따라서 R 지시를 한 번 수행하면 기존 N번 자리의 카드가 새로운 1번 자리의 카드가 된다. R은 카드에 적힌 수를 바꾸거나 카드의 앞뒤를 뒤집는 지시가 아니다. S 지시는 현재 가장 왼쪽에 있는 카드와 가장 오른쪽에 있는 카드를 서로 바꾸라는 뜻이다. 두 카드 사이에 있는 다른 카드의 위치는 바뀌지 않는다. 카드가 한 장뿐이라면 R과 S 중 어떤 지시를 수행해도 배치는 그대로다. 카드가 두 장일 때에는 두 지시의 결과가 같을 수 있지만, 지시는 항상 적힌 순서대로 모두 수행한다. 직원은 Q개의 지시를 위에서부터 차례대로 수행한다. 각 지시는 바로 앞 지시까지 처리한 현재 배치에 적용하며, 처음 배치를 기준으로 따로 적용하지 않는다. 지시가 하나도 없다면 처음 배치를 최종 배치로 사용한다. 카드의 수는 처리 과정에서 늘거나 줄지 않는다. 모든 지시를 수행한 뒤 1번 자리부터 N번 자리까지 놓인 카드에 적힌 수를 구한다. 카드의 원래 번호나 이동 횟수는 출력하지 않으며, 최종 배치를 왼쪽부터 읽은 수열만 출력한다.

입력

첫째 줄에 카드의 수 N과 지시의 수 Q가 공백으로 구분되어 주어진다.
둘째 줄에 처음 배치에서 왼쪽부터 각 카드에 적힌 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
다음 Q개의 줄에는 지시를 나타내는 문자 R 또는 S가 하나씩 주어진다.
N, Q와 카드에 적힌 수는 정수이며 1 ≤ N ≤ 100,000, 0 ≤ Q ≤ 100,000, 0 ≤ A_i ≤ 1,000,000이다.

출력

모든 지시를 수행한 뒤 왼쪽부터 카드에 적힌 수 N개를 공백으로 구분하여 한 줄에 출력한다.

5 3
2 7 4 9 1
R
S
R

1 9 2 7 4

1 4
8
S
R
R
S

8

4 0
6 6 1 3

6 6 1 3

출처: Devin.KR 자체 제작