당신은 놀이기구의 대기열을 관리하고 있습니다. 처음에는 대기열에 아무도 없습니다.
앞으로 $Q$ 개의 쿼리를 순서대로 처리해야 합니다. 쿼리는 다음 4종류 중 하나입니다.
• `A X`: 대기열의 맨 뒤에 이름이 $X$ 인 사람을 추가합니다.
• `B X`: 대기열의 **정중앙**에 이름이 $X$ 인 사람을 삽입합니다. (현재 대기열에 $n$ 명이 있을 때, $n$ 이 짝수라면 앞에서 $n/2$ 번째 사람 뒤에, $n$ 이 홀수라면 앞에서 $(n+1)/2$ 번째 사람 뒤에 삽입합니다. $n=0$ 이면 맨 앞에 추가됩니다.)
• `C`: 대기열의 맨 앞에 있는 사람이 놀이기구에 탑승하여 대기열에서 나갑니다.
• `D`: 대기열의 맨 앞에 있는 사람의 이름을 출력합니다.

[제약 조건]
• $1 \le Q \le 100{,}000$
• 사람의 이름 $X$ 는 영소문자로 구성된 길이 $1$ 이상 $15$ 이하의 문자열입니다.
• `C` 및 `D` 쿼리가 주어질 때 대기열에는 적어도 한 명 이상의 사람이 존재함이 보장됩니다.
• `D` 쿼리가 적어도 한 번 이상 주어집니다.

첫째 줄에 쿼리의 개수 $Q$ 가 주어집니다.
둘째 줄부터 $Q$ 개의 줄에 걸쳐 각 쿼리가 주어집니다.

각 `D` 쿼리에 대해 대기열 맨 앞 사람의 이름을 한 줄에 하나씩 출력하십시오.

6
A kyopuro
A tessoku
B book
D
C
D

kyopuro
book