#include<bits/stdc++.h> using namespace std; #define ll long long int dep[300300],fa[300300][21]; vector<int>g[300400]; inline void dfs(int u){ dep[u]=dep[fa[u][0]]+1; for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v:g[u])if(v!=fa[u][0]){ fa[v][0]=u; dfs(v); } } inline int LCA(int u,int v){ if(dep[u]<dep[v])swap(u,v); int L=20; while(dep[u]>dep[v]){ if(dep[fa[u][L]]>=dep[v]) u=fa[u][L]; L--; } L=20; if(u==v)return u; while(L>=0){ if(fa[u][L]!=fa[v][L]) u=fa[u][L],v=fa[v][L]; L--; } return fa[u][0]; } int rt[300400]; struct node{ int lc,rc; ll mn,mx,tg; }T[32000000]; #define lc(x) T[x].lc #define rc(x) T[x].rc #define mn(x) T[x].mn #define mx(x) T[x].mx #define tg(x) T[x].tg inline void add(int x,ll k){ mn(x)+=k; tg(x)+=k; mx(x)+=k; } // inline void pd(int x){ // if(!tg(x))return ; // if(lc(x))add(lc(x),tg(x)); // if(rc(x))add(rc(x),tg(x)); // tg(x)=0; // } inline void upd(int x){ mn(x)=min(mn(lc(x)),mn(rc(x)))+tg(x); mx(x)=max(mx(lc(x)),mx(rc(x)))+tg(x); } inline int merge(int x,int y){ if(!x||!y)return x|y; tg(x)=tg(lc(x))+tg(rc(x)); lc(x)=merge(lc(x),lc(y)); rc(x)=merge(rc(x),rc(y)); upd(x); return x; } const ll M=998244353,IV2=(M+1)/2; inline ll S(ll l,ll r){ ll a=(l+r)%M,b=(r-l+1)%M; return a*b%M*IV2%M; } const ll INF=1e18; inline ll gmn(int x,int l,int r,int L,int R,ll ex=0){ if(!x)return ex; if(L<=l&&r<=R)return mn(x)+ex; int mid=l+r>>1; ll res=INF; ex+=tg(x); if(L<=mid)res=min(res,gmn(lc(x),l,mid,L,R,ex)); if(R>mid)res=min(res,gmn(rc(x),mid+1,r,L,R,ex)); return res; } inline ll gmx(int x,int l,int r,int L,int R,ll ex=0){ if(!x)return ex; if(L<=l&&r<=R)return mx(x)+ex; int mid=l+r>>1; ll res=-INF; ex+=tg(x); if(L<=mid)res=max(res,gmx(lc(x),l,mid,L,R,ex)); if(R>mid)res=max(res,gmx(rc(x),mid+1,r,L,R,ex)); return res; } inline int gpre(int x,int l,int r,int R,ll lim,ll ex=0){ if(R<l)return -1; if(mn(x)+ex>lim)return -1; if(!x)return min(r,R); if(l==r)return l; int mid=l+r>>1; ex+=tg(x); if(R>mid){ int w=gpre(rc(x),mid+1,r,R,lim,ex); if(w==-1)return gpre(lc(x),l,mid,R,lim,ex); return w; } else return gpre(lc(x),l,mid,R,lim,ex); } int ct=0; inline void mod(int &x,int l,int r,int L,int R,int k){ if(!x)x=++ct; if(L<=l&&r<=R){ add(x,k); return ; } int mid=l+r>>1; if(L<=mid)mod(lc(x),l,mid,L,R,k); if(R>mid)mod(rc(x),mid+1,r,L,R,k); upd(x); } int ANS[300400]; int n,q; vector<pair<int,int>>A[304000]; inline void calc(int rt,int t,int y){ // cout<<t<<" "<<y<<endl; ll bs=gmn(rt,0,q,t,t)-y; int A=gpre(rt,0,q,t,bs); ll RMX=gmx(rt,0,q,A,t); if(A==-1)ANS[t]=-1; else if(A<bs)ANS[t]=(RMX-bs)%M; else{ int B=gpre(rt,0,q,A-1,bs-1); if(B==-1)ANS[t]=S(RMX-bs,INF); else{ ll LMX=gmx(rt,0,q,B,A); if(LMX<=RMX)ANS[t]=(RMX-bs)%M; else ANS[t]=S(RMX-bs,LMX-bs); } } } inline void calc(int u){ for(int v:g[u])if(v!=fa[u][0]) calc(v),rt[u]=merge(rt[u],rt[v]); for(auto e:A[u]) calc(rt[u],e.first,e.second); } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("candy2.in","r",stdin); // freopen("candy.out","w",stdout); T[0]={0,0,0,0,0}; cin>>n>>q; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1); for(int i=1;i<=q;i++){ ANS[i]=-2; int op; cin>>op; if(op!=3){ int a,b,x; cin>>a>>b>>x; if(op==2)x=-x; int l=LCA(a,b); mod(rt[a],0,q,i,q,x); mod(rt[b],0,q,i,q,x); mod(rt[l],0,q,i,q,-x); if(l!=1) mod(rt[fa[l][0]],1,q,i,q,-x); } else{ int a,y; cin>>a>>y; A[a].push_back({i,y}); } } calc(1); for(int i=1;i<=q;i++) if(ANS[i]!=-2)cout<<ANS[i]<<endl; return 0; }