F. Bermart Ice Creamtime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputIn 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). InputThe 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$$$. OutputFor 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).ExampleInput122 1 5 72 1 3 44 1 44 1 84 1 21 12 2 4 104 1 94 2 93 14 1 94 2 9Output4 11 0 11 17 4 17