In the Bermart chain of stores, a variety of ice cream is sold. Each type of ice cream has two parameters: price and tastiness.

Initially, there is one store numbered $$$1$$$, which sells nothing. You have to process $$$q$$$ queries of the following types:

$$$1~x$$$ — a new store opens, that sells the same types of ice cream as store $$$x$$$. It receives the minimum available positive index. The order of the types of ice cream in the new store is the same as in store $$$x$$$.
$$$2~x~p~t$$$ — a type of ice cream with price $$$p$$$ and tastiness $$$t$$$ becomes available in store $$$x$$$.
$$$3~x$$$ — a type of ice cream that was available the longest (appeared the earliest) in store $$$x$$$ is removed.
$$$4~x~p$$$ — for store $$$x$$$, find the maximum total tastiness of a subset of types of ice cream that are sold there, such that the total price does not exceed $$$p$$$ (each type can be used in the subset no more than once).

Input

The first line contains a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^4$$$) — the number of queries.

Each of the following $$$q$$$ lines contains a query in the format described in the statement:

$$$1~x$$$;
$$$2~x~p~t$$$ ($$$1 \le p, t \le 2000$$$);
$$$3~x$$$;
$$$4~x~p$$$ ($$$1 \le p \le 2000$$$).

Additional constraints on the input data:

$$$x$$$ in each query does not exceed the current number of stores (that is, $$$1$$$ plus the number of type $$$1$$$ queries);
query type $$$3$$$ is not applied to a store that has no types of ice cream;
there is at least one query of type $$$4$$$.

Output

For each query of type $$$4$$$, output a single integer — for store $$$x$$$, find the maximum total tastiness of a subset of types of ice cream that are sold there, such that the total price does not exceed $$$p$$$ (each type can be used in the subset no more than once).

Bermart Ice Cream

Examples