양방향 우선순위 큐

다중집합 $S=\lbrace S_1, \ldots, S_N \rbrace$이 주어진다. 다음 $Q$개의 쿼리를 순서대로 처리한다:

• 0 x: $x$을 $S$에 추가한다.
• 1: $S$의 최솟값인 원소 중 하나를 출력하고, 이를 $S$에서 제거한다.
• 2: $S$의 최댓값인 원소 중 하나를 출력하고, 이를 $S$에서 제거한다.

유형이 1 또는 2인 쿼리를 처리할 때 $S$이 비어 있지 않음이 보장된다.

제약 조건

• $0 \leq N \leq 500000$
• $1 \leq Q \leq 500000$
• $-1000000000 \leq S _ i, x \leq 1000000000$

$N\; Q$
$S_1 \cdots S_N$
$\mathrm{Query}_0$
$\vdots$
$\mathrm{Query}_{Q-1}$

1: $S$의 최솟값인 원소 중 하나를 출력하고, 이를 $S$에서 제거한다.

2: $S$의 최댓값인 원소 중 하나를 출력하고, 이를 $S$에서 제거한다.