새들의 의식

새는 놀라운 동물이다. 공작의 구애 춤부터 붉은머리마나킨의 문워크까지, 많은 종이 살아가면서 여러 의식을 펼친다. 이 문제에서는 그중에서도 순열 춤을 다룬다. 이 의식은 그림처럼 전선이나 나뭇가지 위에 한 줄로 앉은 새 무리가 펼친다.

이 의식은 다음 종류의 동작을 순서대로 수행하는 공연으로 단순화할 수 있다.

• 삽입: 새 한 마리가 무리에 합류해 새 줄의 어딘가에 끼어든다.
• 이탈: 줄에 있던 새 한 마리가 남은 의식 동안 무리를 떠나 날아간다.
• 이동: 줄에 있던 새 한 마리가 자기 자리에서 날아가 줄의 다른 어딘가에 앉는다(끼어든다).

줄에서 새들의 처음 위치와 동작의 순서가 주어질 때, 의식이 끝난 뒤 새들의 최종 위치를 구하라.

첫 줄에 공백으로 구분된 두 정수 n (1 ⩽ n ⩽ 1000)과 s (1 ⩽ s ⩽ 5000)가 주어진다. 둘째 줄에는 의식의 처음 배치, 즉 줄에 있는 새들의 위치를 왼쪽에서 오른쪽 순서로 나타내는 n개의 새 이름이 공백으로 구분되어 주어진다. 각 새 이름은 길이가 10 이하인 비어 있지 않은 (소문자) 영숫자 문자열이다(a부터 z, 0부터 9).

동작의 순서는 다음 s개 줄에 한 줄에 하나씩 주어진다. 각 줄은 동작 종류에 따라 다음 형식 중 하나를 따른다. 동작에 나오는 bird-name 매개변수는 입력의 둘째 줄과 같은 형식이다.

• 삽입: insert bird-name position

position 매개변수는 삽입 위치의 왼쪽에 있는 새의 수를 나타내는 정수다. 이 매개변수는 [0, M] 범위에 있다. 여기서 M은 삽입 전 줄에 있는 새의 총수다. 위치 0은 새를 줄의 맨 앞(가장 왼쪽)에 놓고, 위치 M은 줄의 맨 뒤(가장 오른쪽)에 놓는다.

• 이탈: depart bird-name
• 이동: relocate bird-name displacement

displacement 매개변수는 양수, 음수, 0이 될 수 있는 정수다. 변위가 0이면 새는 자기 자리로 날아간다. 그렇지 않으면 변위가 양수(음수)일 때 새는 오른쪽(왼쪽)의 새 k마리를 넘어서 날아간다. 여기서 k는 변위의 절댓값이다. 이 매개변수는 [−L, +R] 범위에 있다. 여기서 L과 R은 각각 이동 전 줄에서 움직이는 새의 왼쪽과 오른쪽에 있는 새의 수다. 변위 −L은 새를 줄의 맨 앞(가장 왼쪽)에 놓고, 변위 +R은 줄의 맨 뒤(가장 오른쪽)에 놓는다.

의식에 참여하는 새 중 이름이 같은 새는 없다. 또한 모든 동작은 실행되는 순간에 의미가 있으며, 의식 내내 나뭇가지 위에 새가 항상 한 마리 이상 있다고 보장된다.

의식의 최종 배치를 한 줄에 출력한다. 줄에는 줄에 있는 새들의 이름이 왼쪽에서 오른쪽 순서로 공백으로 구분되어 있어야 한다.

처음 두 예제 입력의 영상이 첨부 패키지에 있다. 저작권 고지: 이 문제의 이미지와 영상은 다음 주소에서 가져왔다.

• Animation “For the Birds”, Pixar Animation Studios
• https://www.instagram.com/p/BpBshBghJ54/
• https://www.instagram.com/p/B1XWKQXgGKe/