31031번 - 마비노기 가방 정리하기

문제

마비노기에는 가방 안에 담을 수 있는 물건의 면적이 한정되어 있기 때문에, 정후는 마비노기를 하다가 가방 공간이 턱없이 부족해졌다. 마비노기에서 $R\times C$ 크기의 가방은 $R$행 $C$열의 격자 $RC$ 개로 이루어진 직사각형 모양이다. 또한, $x\times y$ 크기의 물건은 가방에서 $x$행 $y$열의 연속한 격자 공간을 차지한다. 물건은 회전할 수 없고, 서로 다른 물건은 서로 겹칠 수 없으며, 가방 경계를 벗어날 수 없다. 정후는 직사각형 모양 가방을 정리해 담을 수 있는 물건의 가치의 합을 최대화하고자 한다.

처음에 정후는 물건이나 가방을 가지고 있지 않다.

정후는 $Q$ 회에 걸쳐 물건을 새로 습득하거나 버리거나, 가방을 새로 구매하거나 버린다. 이는 다음과 같은 형식으로 기록된다.

• 1 R C : 정후가 $R\times C$ 크기의 가방을 새로 구매한다. 이 가방을 다른 가방 안에 넣을 필요는 없으며, 가방을 구매하는 데 드는 비용은 생각하지 않는다.
• 2 x y w : 정후가 $x\times y$ 크기, 가치 $w$의 물건을 습득한다. 한 번이라도 습득한 물건의 가치는 모두 서로 다르다.
• 3 e : $e$번 기록에서 구매한 가방이나 습득한 물건을 버린다.

정후는 매 기록 이후 가방에 담을 수 있는 물건의 가치의 합의 최댓값을 알고 싶다. 기록마다 가방에 물건을 담는 방법은 독립이다. 정후를 도와주자.

입력

첫 번째 줄에 기록의 수 $Q$가 주어진다.

이후 $Q$ 개의 줄에 정후가 물건을 새로 습득하거나 버리거나, 가방을 새로 구매하거나 버린 기록이 주어진 형식에 맞게 주어진다.

출력

매 기록 이후 정후가 가방에 담을 수 있는 물건의 가치의 합의 최댓값을 나타내는 정수를 한 줄에 하나씩 출력한다. 물건을 담을 수 없다면 0을 출력한다.

제한

• 1ドル \leq Q \leq 30,000円$
• 1ドル \leq R, C \leq 60,000円$
• 1ドル \leq w \leq 10^9$
• 한 번이라도 습득한 물건의 가치는 모두 서로 다르다.
• 1ドル \leq x, y \leq 2$
• 1ドル \leq e \leq Q$
• 3 $e$ 기록은 항상 올바른 기록이다. 즉, $e$ 번 기록은 이전에 주어진 물건이나 가방을 추가하는 기록이며, $e$는 서로 다르다.
• 주어지는 모든 수는 정수이다.

힌트