마비노기 가방 정리하기

마비노기에서는 가방에 담을 수 있는 물건의 면적이 한정되어 있어서, 정후는 가방 공간이 턱없이 부족해졌다. 마비노기의 $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$는 서로 다르다.
• 주어지는 모든 수는 정수이다.