수족관의 양방향 급식 수로

문제

수족관에는 물고기들이 한 줄로 기다리는 긴 급식 수로가 있다. 수로의 양 끝은 왼쪽과 오른쪽으로 구분하며, 물고기의 줄은 처음에 비어 있다. 각 물고기에는 양의 정수로 된 표식 값이 붙어 있다. 표식 값은 기록에 사용하는 수치이므로 서로 다른 물고기에 같은 값이 붙어 있어도 된다. 수로 안에서 물고기끼리 서로 앞지르는 일은 없으며, 물고기의 위치는 아래에서 설명하는 명령에 의해서만 바뀐다. 수로에는 물고기가 먹이를 받고 빠져나가는 급식 출구가 있다. 출구는 왼쪽 끝이나 오른쪽 끝 중 하나로 설정할 수 있고, 처음에는 왼쪽 끝으로 설정되어 있다. 관리 장치에는 IN, TURN, FEED의 세 종류 명령이 순서대로 기록된다. 각 명령은 앞선 명령의 처리가 모두 끝난 뒤에 실행된다. IN X는 표식 값이 X인 새 물고기 한 마리를 수로의 오른쪽 끝에 넣는 명령이다. 급식 출구가 어느 쪽으로 설정되어 있더라도 새 물고기는 항상 오른쪽 끝에 들어간다. TURN은 급식 출구를 반대쪽 끝으로 바꾸는 명령이다. 왼쪽이면 오른쪽으로, 오른쪽이면 왼쪽으로 바꾼다. 이때 수로 안의 물고기들이 실제로 이동하거나 줄의 좌우 순서가 뒤집히는 것은 아니다. 수로가 비어 있어도 출구 설정은 바뀐다. FEED K는 현재 급식 출구에 가장 가까운 물고기부터 최대 K마리에게 먹이를 주는 명령이다. 먹이를 받은 물고기는 즉시 수로에서 빠져나가며 다시 들어오지 않는다. 수로에 K마리보다 적은 물고기가 있다면 남아 있는 물고기 모두에게 먹이를 준다. 각 FEED 명령마다 그 명령으로 빠져나간 물고기들의 표식 값 합을 기록해야 한다. 아무 물고기도 빠져나가지 않았다면 기록할 합은 0이다. 전체 명령을 주어진 순서대로 처리하고, FEED 명령이 등장할 때마다 기록해야 할 합을 구한다. 같은 표식 값을 가진 물고기도 각각 별개의 한 마리로 처리한다. 출력에는 물고기별 표식이나 마지막 줄 상태를 적지 않고 각 급식 기록만 명령 순서대로 적는다.

입력

첫째 줄에 명령 수 N이 주어진다. N은 1 이상 30,000 이하의 정수다.
다음 N개 줄에 명령 하나씩이 주어진다. 각 명령은 IN X, TURN, FEED K 중 하나다. X는 1 이상 1,000,000 이하의 정수이며, K는 1 이상 30,000 이하의 정수다.
FEED 명령이 적어도 하나 주어진다.

출력

각 FEED 명령에 대해 빠져나간 물고기들의 표식 값 합을 정수로 한 줄에 하나씩 출력한다. 출력 순서는 FEED 명령의 입력 순서와 같아야 한다. 빠져나간 물고기가 없으면 0을 출력한다.

10
IN 8
IN 3
IN 6
FEED 1
TURN
IN 5
FEED 2
TURN
FEED 4
FEED 1

8
11
3
0

7
TURN
FEED 2
IN 7
IN 7
FEED 1
TURN
FEED 3

0
7
7

출처: Devin.KR 자체 제작