CF2026F Bermart Ice Cream

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).

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 $ .

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).