Organizing Bags in Mabinogi

In Mabinogi, the area of items you can carry in a bag is limited, so Jeonghu has run out of bag space. A $R\times C$ bag in Mabinogi is a rectangle made of $R$ rows and $C$ columns, which is $RC$ grid cells in total. An item of size $x\times y$ occupies a contiguous block of $x$ rows and $y$ columns in the bag. Items cannot be rotated, different items cannot overlap, and no item can extend past the bag boundary. Jeonghu wants to organize a rectangular bag so that the total value of the items inside is maximized.

At first, Jeonghu has no items and no bags.

Over $Q$ records, Jeonghu acquires or discards items, and buys or discards bags. Each record is given in one of the following formats.

• 1 R C: Jeonghu buys a new $R\times C$ bag. This bag does not need to be placed inside another bag, and the cost of buying a bag is not considered.
• 2 x y w: Jeonghu acquires an item of size $x\times y$ with value $w$. The values of all items ever acquired are distinct.
• 3 e: Jeonghu discards the bag or item that was acquired in record $e$.

After each record, Jeonghu wants to know the maximum total value of items that can be packed into the bag. Each record is handled independently when packing items. Help Jeonghu.

The first line contains the number of records $Q$.

The next $Q$ lines each contain one record in the format described above, which records that Jeonghu acquired or discarded an item, or bought or discarded a bag.

After each record, print on its own line the maximum total value of items that can be packed into the bag. If no item can be packed, print 0.

• $1 \leq Q \leq 30\,000$
• $1 \leq R, C \leq 60\,000$
• $1 \leq w \leq 10^9$
• The values of all items ever acquired are distinct.
• $1 \leq x, y \leq 2$
• $1 \leq e \leq Q$
• Record 3 e is always valid. That is, record $e$ is a earlier record that bought a bag or acquired an item, and the values of $e$ are distinct.
• All given numbers are integers.