F. Мороженое в Бермарте
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В сети магазинов Бермарт продается мороженое. У каждого сорта мороженого есть два параметра: цена и вкусность.

Изначально есть один магазин с номером $$$1$$$, в котором ничего не продаётся. Требуется обработать $$$q$$$ запросов следующих типов:

  • $$$1~x$$$ — открывается новый магазин, в котором продаются те же сорта мороженого, что и в магазине $$$x$$$. Он получает первый свободный порядковый номер. Порядок появления сортов мороженого в новом магазине тот же, что и в магазине $$$x$$$.
  • $$$2~x~p~t$$$ — в магазине $$$x$$$ в продаже появляется сорт мороженого с ценой $$$p$$$ и вкусностью $$$t$$$.
  • $$$3~x$$$ — в магазине $$$x$$$ исчезает из продажи сорт мороженого, который там появился раньше всего.
  • $$$4~x~p$$$ — для магазина $$$x$$$ надо найти максимальную суммарную вкусность поднабора сортов, которые там продаются, так, чтобы суммарная цена не превышала $$$p$$$ (каждый сорт можно использовать в поднаборе не более одного раз).
Входные данные

В первой строке записано одно целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^4$$$) — количество запросов.

В каждой из $$$q$$$ следующих строк записан очередной запрос в формате, описанном в условии:

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

Дополнительные ограничения на входные данные:

  • $$$x$$$ в каждом запросе не превышает текущего количества магазинов (то есть, $$$1$$$ плюс количество запросов типа $$$1$$$);
  • запрос типа $$$3$$$ не применяется к магазину, в котором нет ни одного типа мороженого;
  • есть хотя бы один запрос типа $$$4$$$.
Выходные данные

На каждый запрос типа $$$4$$$ выведите одно целое число — для магазина $$$x$$$ найдите максимальную суммарную вкусность поднабора сортов, которые там продаются, так, чтобы суммарная цена не превышала $$$p$$$ (каждый сорт можно использовать в поднаборе не более одного раз).

Пример
Входные данные
12
2 1 5 7
2 1 3 4
4 1 4
4 1 8
4 1 2
1 1
2 2 4 10
4 1 9
4 2 9
3 1
4 1 9
4 2 9
Выходные данные
4
11
0
11
17
4
17