CF1515I.Phoenix and Diamonds

Phoenix wonders what it is like to rob diamonds from a jewelry store!

There are $n$ types of diamonds. The $i$-th type has weight $w_i$ and value $v_i$. The store initially has $a_i$ diamonds of the $i$-th type.

Each day, for $q$ days, one of the following will happen:

1. A new shipment of $k_i$ diamonds of type $d_i$ arrive.
2. The store sells $k_i$ diamonds of type $d_i$.
3. Phoenix wonders what will happen if he robs the store using a bag that can fit diamonds with total weight not exceeding $c_i$. If he greedily takes diamonds of the largest value that fit, how much value would be taken? If there are multiple diamonds with the largest value, he will take the one with minimum weight. If, of the diamonds with the largest value, there are multiple with the same minimum weight, he will take any of them.

Of course, since Phoenix is a law-abiding citizen, this is all a thought experiment and he never actually robs any diamonds from the store. This means that queries of type $3$ do not affect the diamonds in the store.

凤凰好奇，抢劫珠宝店的钻石会是什么感觉！

共有 $n$ 种钻石。第 $i$ 种钻石的重量为 $w_i$，价值为 $v_i$。商店初始时拥有第 $i$ 种钻石 $a_i$ 颗。

接下来共 $q$ 天，每天会发生以下三种事件之一：

1. 新到一批 $k_i$ 颗第 $d_i$ 种钻石；
2. 店铺售出 $k_i$ 颗第 $d_i$ 种钻石；
3. 凤凰思考：若他用一个承重上限为 $c_i$ 的背包去“抢劫”该店，且采用贪心策略——每次优先选取价值最大、同时仍能装入背包的钻石；当存在多个价值最大的钻石时，选择其中重量最小的一个；若仍有多个钻石满足“价值最大且重量最小”，则任选其一——那么最终能获得的总价值是多少？

当然，由于凤凰是一名遵纪守法的好公民，这仅是一场思想实验，他绝不会真正从店里抢劫任何钻石。这意味着类型 $3$ 的查询不会改变店内钻石的数量。

The first line contains two integers $n$ and $q$ ($1 \le n \le 2 \cdot 10^5$; $1 \le q \le 10^5$) — the number of types of diamonds and number of days, respectively.

The next $n$ lines describe each type of diamond. The $i$-th line will contain three integers $a_i$, $w_i$, and $v_i$ ($0 \le a_i \le 10^5$; $1 \le w_i, v_i \le 10^5$) — the initial number of diamonds of the $i$-th type, the weight of diamonds of the $i$-th type, and the value of diamonds of the $i$-th type, respectively.

The next $q$ lines contain the queries. For each query, the first integer of each line is $t$ ($1 \le t \le 3$) — the type of query.

If $t=1$, then two integers $k_i$, $d_i$ follow ($1 \le k_i \le 10^5$; $1 \le d_i \le n$). This means that a new shipment of $k_i$ diamonds arrived, each of type $d_i$.

If $t=2$, then two integers $k_i$, $d_i$ follow ($1 \le k_i \le 10^5$; $1 \le d_i \le n$). This means that the store has sold $k_i$ diamonds, each of type $d_i$. It is guaranteed that the store had the diamonds before they sold them.

If $t=3$, an integer $c_i$ will follow ($1 \le c_i \le 10^{18}$) — the weight capacity of Phoenix's bag.

It is guaranteed that there is at least one query where $t=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$ 种钻石的初始数量、单颗重量以及单颗价值。

接下来的 $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$ 的查询。

Print the answer for each query of the third type ($t=3$).

输出每个第三类查询（$t=3$）的答案。

For the first query where $t=3$, Phoenix can fit $2$ diamonds of type $1$, with total weight $6$ and value $8$.

For the second query where $t=3$, Phoenix will first fit in $3$ diamonds of type $3$, then one diamond of type $1$ for a total weight of $9$ and a value of $16$. Note that diamonds of type $3$ are prioritized over type $1$ because type $3$ has equal value but less weight.

For the final query where $t=3$, Phoenix can fit every diamond for a total value of $13$.

对于第一个查询（$t=3$），凤凰可以装入 $2$ 颗类型 $1$ 的钻石，总重量为 $6$，总价值为 $8$。

对于第二个查询（$t=3$），凤凰将首先装入 $3$ 颗类型 $3$ 的钻石，再装入 $1$ 颗类型 $1$ 的钻石，总重量为 $9$，总价值为 $16$。注意：类型 $3$ 的钻石优先于类型 $1$ 的钻石，因为它们的价值相同但重量更小。

对于最后一个查询（$t=3$），凤凰可以装入所有钻石，总价值为 $13$。