매니저

병렬 처리에서 흔히 쓰이는 방식 중 하나는 생산자/소비자 패러다임으로, 하나의 매니저(manager) 프로세스와 여러 개의 클라이언트(client) 프로세스로 이루어진 시스템으로 구현할 수 있다. 클라이언트는 생산자, 소비자 등이 될 수 있다. 매니저는 클라이언트 프로세스들을 관리한다. 각 프로세스는 비용(cost) 으로 구분되며, 비용은 $1 \le \text{cost} \le 10000$ 범위의 강한 양의 정수이다. 같은 비용을 가진 프로세스의 개수는 10000을 넘지 않는다. 매니저는 큐를 관리하며 다음 네 종류의 요청을 처리한다.

• a x — 비용이 $x$인 프로세스를 큐에 추가한다.
• r — 현재 정책에 따라 큐에서 프로세스 하나를 (가능하다면) 제거한다.
• p i — 매니저의 정책을 $i$로 설정한다. $i$는 1 또는 2이며, 기본 정책은 1이다.
• e — 요청 목록을 끝낸다.

매니저 정책은 두 가지이다.

• 정책 1 — 비용이 최소인 프로세스를 제거한다.
• 정책 2 — 비용이 최대인 프로세스를 제거한다.

매니저는 어떤 제거 요청의 순번이 출력 목록에 있을 때에만 그 제거된 프로세스의 비용을 출력한다.

매니저를 시뮬레이션하는 프로그램을 작성하여라.

각 데이터 집합의 형식은 다음과 같다.

• 프로세스의 최대 비용
• 출력 목록의 길이
• 출력 목록 — 결과를 출력할 제거 요청들의 순번 (예를 들어 1 4는 첫 번째와 네 번째 제거 요청으로 제거된 비용을 출력한다는 뜻이다)
• 요청 목록 (각 요청은 한 줄에 하나씩)

각 데이터 집합은 e 요청으로 끝난다. 서로 다른 데이터 집합은 빈 줄로 구분된다.

순번이 출력 목록에 있는 각 제거 요청에 대해, 제거된 프로세스의 비용을 출력한다. 그 시점에 큐가 비어 있으면 대신 -1을 출력한다. 각 출력값은 한 줄에 하나씩 쓰고, 서로 다른 데이터 집합의 결과 사이에는 빈 줄을 하나 넣는다.