首先 \(c\) 很大，因此复杂度跟 \(c\) 有关的项肯定只能是 \(\log c\) 之类的。
类比 IOI2021 dungeons 的套路，我们对值域进行分层，假设 \(c\in[2^{\omega-1},2^{\omega})\)，考虑令重量在 \(\ge 2^{\omega-1}\) 的物品为“重物品”，其他物品为“轻物品”，那么一个显然的性质是我们最多只能取一个“重物品”。并且如果取了一个“重物品”，那么 \(c\) 就会进入 \(\omega\) 以下的层。如果存在一个“轻物品”，满足其不能取完全部 \(a_i\) 个，那么说明此时 \(c<w_i<2^{\omega-1}\)，也会进入 \(\omega\) 以下的层。
考虑将这个过程放在线段树上。对线段树上每个节点 \([l,r]\) 维护以下三个信息：
- \(lw_i\)：\([l,r]\) 中所有重量 \(<2^{i-1}\) 的物品的 \(w_j·a_j\) 之和。
- \(lv_i\)：\([l,r]\) 中所有重量 \(<2^{i-1}\) 的物品的 \(v_j·a_j\) 之和。
- \(tot_i\)：要取走至少一个 \([l,r]\) 中重量在 \([2^{i-1},2^i)\) 中物品，\(c\) 至少为多少。
显然这些信息都可以在 \(O(\log V)\) 的时间内进行 pushup。具体细节见代码。
接下来怎么考虑查询。假设现在递归到 \([l,r]\) 表示的节点，\(c\in[2^{\omega},2^{\omega+1})\)，特判掉以下两种情况：
- \(c\ge lw_{\omega}\)，说明所有可能能取走的物品都能取走，直接返回 \(lv_{\omega}\)。
- \(lw_{\omega-1}\le c<tot_{\omega-1}\)，说明所有轻物品都能取走，但重物品一个都不能取。直接返回 \(lv_{\omega-1}\)。
除此之外的所有情况都继续递归两个子节点。可以证明复杂度为 \(O(\log V\log n)\)，这是因为对于第三种情况，要么你取走了一个重物品，要么遇到某个轻物品不能全部取完，根据前面的分析，此种情况都会使 \(c\) 至少减一，因此递归两个分叉的次数不会超过 \(\log V\)。
const int MAXN=2e5;
const int LOG_V=18;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,qu,w[MAXN+5],v[MAXN+5],ord[MAXN+5],pos[MAXN+5],omega;ll a[MAXN+5],c;
bool cmp(int x,int y){return ((v[x]==v[y])?(w[x]<w[y]):(v[x]>v[y]));}
struct node{int l,r;ll lw[LOG_V+2],lv[LOG_V+2],tot[LOG_V+2];}s[MAXN*4+5];
void pushup(int k){
for(int i=1;i<=LOG_V;i++){
s[k].lw[i]=s[k<<1].lw[i]+s[k<<1|1].lw[i];
s[k].lv[i]=s[k<<1].lv[i]+s[k<<1|1].lv[i];
s[k].tot[i]=min(s[k<<1].tot[i],s[k<<1|1].tot[i]+s[k<<1].lw[i]);
}
}
void init_val(int k,int p){
for(int i=1;i<=18;i++){
s[k].lw[i]=s[k].lv[i]=0;s[k].tot[i]=INF;
if(w[p]<(1<<i-1))s[k].lv[i]=1ll*v[p]*a[p],s[k].lw[i]=1ll*w[p]*a[p];
else if(w[p]<(1<<i)&&a[p]>0)s[k].tot[i]=w[p];
}
}
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r)return init_val(k,ord[l]),void();
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);
}
void modify(int k,int p){
if(s[k].l==s[k].r)return init_val(k,ord[p]),void();
int mid=s[k].l+s[k].r>>1;
if(p<=mid)modify(k<<1,p);else modify(k<<1|1,p);
pushup(k);
}
void recalc(){while(omega>1&&(1<<((omega-1)-1))>c)omega--;}
ll query(int k){
if(s[k].l==s[k].r){
ll num=min(a[ord[s[k].l]],c/w[ord[s[k].l]]);
c-=num*w[ord[s[k].l]];recalc();return num*v[ord[s[k].l]];
}
if(s[k].lw[omega]<=c){ll tmp=s[k].lv[omega];c-=s[k].lw[omega];recalc();return tmp;}
else if(s[k].lw[omega-1]<=c&&c<s[k].tot[omega-1]){ll tmp=s[k].lv[omega-1];c-=s[k].lw[omega-1];recalc();return tmp;}
else return query(k<<1)+query(k<<1|1);
}
int main(){
scanf("%d%d",&n,&qu);
for(int i=1;i<=n;i++)scanf("%lld%d%d",&a[i],&w[i],&v[i]),ord[i]=i;
sort(ord+1,ord+n+1,cmp);for(int i=1;i<=n;i++)pos[ord[i]]=i;
build(1,1,n);
while(qu--){
int opt;scanf("%d",&opt);
if(opt==1||opt==2){
int k,d;scanf("%d%d",&k,&d);
a[d]+=((opt==1)?k:(-k));
modify(1,pos[d]);
}else{
scanf("%lld",&c);omega=18;recalc();
printf("%lld\n",query(1));
}
}
return 0;
}