I. Феникс и бриллианты
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Фениксу стало интересно: какого это — красть бриллианты из ювелирного магазина!

Всего есть $$$n$$$ видов бриллиантов: бриллиант $$$i$$$-го вида весит $$$w_i$$$ и стоит $$$v_i$$$. Первоначально в магазине есть $$$a_i$$$ бриллиантов $$$i$$$-го вида.

Каждый день, на протяжении $$$q$$$ дней, происходит одно из следующих событий:

  1. В магазин поступает $$$k_i$$$ бриллиантов вида $$$d_i$$$.
  2. Магазин продает $$$k_i$$$ бриллиантов вида $$$d_i$$$.
  3. Феникс интересуется, что произойдет, если он решит ограбить магазин, придя в него с мешком, который может вместить бриллианты суммарным весом не более $$$c_i$$$. Если Феникс будет брать бриллианты жадно начиная с самых дорогих, бриллиантов на какую стоимость он наберет? Если есть несколько бриллиантов с максимальной стоимостью, он будет брать сначала самые легкие. Если же среди бриллиантов с максимальной стоимостью есть несколько с минимальным весом, то он берет любой из них.

Конечно же, так как Феникс — законопослушный гражданин, то все описанное выше — не более чем мысленный эксперимент и он никогда не будет по-настоящему забирать бриллианты из магазина. Другими словами, запросы типа $$$3$$$ не влияют на количество бриллиантов в магазине.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 10^5$$$) — количество видов бриллиантов и количество дней, соответственно.

В следующих $$$n$$$ строках описаны каждый из видов бриллиантов. В $$$i$$$-й строке заданы три целых числа $$$a_i$$$, $$$w_i$$$ и $$$v_i$$$ ($$$0 \le a_i \le 10^5$$$; $$$1 \le w_i, v_i \le 10^5$$$) — первоначальное количество бриллиантов $$$i$$$-го вида, вес бриллианта $$$i$$$-го вида и стоимость бриллианта $$$i$$$-го вида, соответственно.

В следующих $$$q$$$ строках заданы запросы. Для каждого запроса, первое число в строке $$$t$$$ ($$$1 \le t \le 3$$$) — это тип запроса.

Если $$$t=1$$$, то далее заданы два целых числа $$$k_i$$$ и $$$d_i$$$ ($$$1 \le k_i \le 10^5$$$; $$$1 \le d_i \le n$$$) означающие, что в магазин поступает $$$k_i$$$ бриллиантов вида $$$d_i$$$.

Если $$$t=2$$$, то далее заданы два целых числа $$$k_i$$$ и $$$d_i$$$ ($$$1 \le k_i \le 10^5$$$; $$$1 \le d_i \le n$$$) означающие, что магазин продает $$$k_i$$$ бриллиантов вида $$$d_i$$$. Гарантируется, что в магазине действительно было необходимое количество бриллиантов.

Если $$$t=3$$$, то далее задано одно целое число $$$c_i$$$ ($$$1 \le c_i \le 10^{18}$$$) — суммарный вес, который выдерживает мешок Феникса.

Гарантируется, что есть хотя бы один запрос, где $$$t=3$$$.

Выходные данные

Выведите ответ для каждого запроса третьего типа ($$$t=3$$$).

Пример
Входные данные
3 5
2 3 4
1 5 1
0 2 4
3 6
1 3 3
3 10
2 2 3
3 30
Выходные данные
8
16
13
Примечание

В первом запросе с $$$t=3$$$, Феникс может уместить $$$2$$$ бриллианта вида $$$1$$$, с общим весом $$$6$$$ и стоимостью $$$8$$$.

Во втором запросе с $$$t=3$$$, Феникс может забрать $$$3$$$ бриллианта вида $$$3$$$ и еще один вида $$$1$$$. Общий вес будет равен $$$9$$$, а стоимость — $$$16$$$. Заметим, что бриллианты вида $$$3$$$ предпочтительнее, чем вида $$$1$$$, потому что вид $$$3$$$ при равной стоимости имеет меньший вес.

В последнем запросе с $$$t=3$$$, Феникс может забрать все бриллианты с общей стоимостью $$$13$$$.