34198번 - 변형된 회전하는 큐

문제

서로 다른 양의 정수 $N$개 $a_1, a_2, \cdots, a_N$을 담고 있는 변형된 양방향 큐가 있다. 변형된 양방향 큐 내에서 실행되는 쿼리가 다음과 같이 주어진다.

• SF: 큐의 첫 번째 원소를 마지막으로 옮긴다. 이 쿼리를 수행하면 큐의 상태가 원래 $b_1, b_2, \cdots, b_M$이었던 것이 $b_2, \cdots, b_M, b_1$로 바뀐다.
• SL: 큐의 마지막 원소를 첫 위치로 옮긴다. 이 쿼리를 수행하면 큐의 상태가 원래 $b_1, \cdots, b_{M-1}, b_M$이었던 것이 $b_M, b_1, \cdots, b_{M-1}$로 바뀐다.
• SM $x$: 큐에 포함된 원소 $x$를 기준으로, $x$의 왼쪽과 오른쪽에 있는 원소들을 서로 맞바꾼다. 이 쿼리를 수행하면 큐의 상태가 원래 $b_1, \cdots, b_{i-1}, x, b_{i+1}, \cdots, b_M$이었던 것이 $b_{i+1}, \cdots, b_M, x, b_1, \cdots, b_{i-1}$로 바뀐다.
• PF: 큐의 첫 번째 원소를 뽑아낸다. 이 쿼리를 수행하면 큐의 상태가 원래 $b_1, b_2, \cdots, b_M$이었던 것이 $b_2, \cdots, b_M$로 바뀐다.
• PL: 큐의 마지막 원소를 뽑아낸다. 이 쿼리를 수행하면 큐의 상태가 원래 $b_1, \cdots, b_{M-1}, b_M$이었던 것이 $b_1, \cdots, b_{M-1}$로 바뀐다.
• PM $x$: 큐에 포함된 원소 $x$를 뽑아낸다. 이 쿼리를 수행하면 큐의 상태가 원래 $b_1, \cdots, b_{i-1}, x, b_{i+1}, \cdots, b_M$이었던 것이 $b_1, \cdots, b_{i-1}, b_{i+1}, \cdots, b_M$로 바뀐다.

큐 내의 모든 원소들을 뽑아내도록 쿼리가 주어진다. 주어진 모든 쿼리를 수행하고 난 뒤, 큐에서 뽑아낸 원소들을 순서대로 출력하는 프로그램을 작성하여라.

입력

첫째 줄에 변형된 양방향 큐에 초기에 포함된 원소 개수 $N$이 주어진다. $(1 \le N \le 300\ 000)$

둘째 줄에 서로 다른 양의 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. $(1 \le a_i \le N)$

셋째 줄에 쿼리의 개수 $Q$가 주어진다. $(N \le Q \le 600\ 000)$

넷째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리에 대한 입력이 주어진다.

큐 내의 모든 원소들을 뽑아내도록 쿼리가 주어지는 것이 보장되며, SM과 PM 쿼리가 주어질 때 원소 $x$는 큐 내에 반드시 포함됨도 보장된다.

출력

주어진 모든 쿼리를 수행하고 난 뒤, 큐에서 뽑아낸 원소들을 공백으로 구분하여 순서대로 출력한다.

제한

힌트