#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a > G; vector vid, head, sub, par, dep, inv, type; HLD(){} HLD(int n): n(n),pos(0),G(n),vid(n,-1),head(n),sub(n,1), par(n,-1),dep(n,0),inv(n),type(n){} void add_edge(int u, int v) { G[u].push_back(v); G[v].push_back(u); } void build(vector rs={0}) { int c=0; for(int r:rs){ dfs_sz(r); head[r]=r; dfs_hld(r,c++); } } void dfs_sz(int v) { for(int &u:G[v]){ if(u==par[v]) continue; par[u]=v; dep[u]=dep[v]+1; dfs_sz(u); sub[v]+=sub[u]; if(sub[u]>sub[G[v][0]]) swap(u,G[v][0]); } } void dfs_hld(int v,int c) { vid[v]=pos++; inv[vid[v]]=v; type[v]=c; for(int u:G[v]){ if(u==par[v]) continue; head[u]=(u==G[v][0]?head[v]:u); dfs_hld(u,c); } } // for_each(vertex) // [l,r] <- attention!! template void for_each(int u, int v, const F& f) { while(1){ if(vid[u]>vid[v]) swap(u,v); f(max(vid[head[v]],vid[u]),vid[v]); if(head[u]!=head[v]) v=par[head[v]]; else break; } } template T for_each(int u,int v,T ti,const Q &q,const F &f){ T l=ti,r=ti; while(1){ if(vid[u]>vid[v]){ swap(u,v); swap(l,r); } l=f(l,q(max(vid[head[v]],vid[u]),vid[v])); if(head[u]!=head[v]) v=par[head[v]]; else break; } return f(l,r); } // for_each(edge) // [l,r] <- attention!! template void for_each_edge(int u, int v,const F& f) { while(1){ if(vid[u]>vid[v]) swap(u,v); if(head[u]!=head[v]){ f(vid[head[v]],vid[v]); v=par[head[v]]; }else{ if(u!=v) f(vid[u]+1,vid[v]); break; } } } int lca(int u,int v){ while(1){ if(vid[u]>vid[v]) swap(u,v); if(head[u]==head[v]) return u; v=par[head[v]]; } } int distance(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; } }; template struct SegmentTree{ using F = function; using G = function; using H = function; int n,height; F f; G g; H h; T ti; E ei; vector dat; vector laz; SegmentTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei){} void init(int n_){ n=1;height=0; while(n &v){ int n_=v.size(); init(n_); for(int i=0;i>i); } inline void recalc(int k){ while(k>>=1) dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } void update(int a,int b,E x){ thrust(a+=n); thrust(b+=n-1); for(int l=a,r=b+1;l>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } recalc(a); recalc(b); } void set_val(int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=ei; recalc(a); } T query(int a,int b){ thrust(a+=n); thrust(b+=n-1); T vl=ti,vr=ti; for(int l=a,r=b+1;l>=1,r>>=1) { if(l&1) vl=f(vl,reflect(l++)); if(r&1) vr=f(reflect(--r),vr); } return f(vl,vr); } }; struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; template struct Mint{ T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0) v+=MOD;} Mint pow(long long k){ Mint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a) const{return Mint(v)+=a;}; Mint operator-(Mint a) const{return Mint(v)-=a;}; Mint operator*(Mint a) const{return Mint(v)*=a;}; Mint operator/(Mint a) const{return Mint(v)/=a;}; Mint operator-(){return v?MOD-v:v;} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} bool operator <(const Mint a)const{return v dp; dp.reserve(sq); Mint res(1); for(int r=0;r0) return idx; } res*=p; } return T(-1); } static vector fact,finv,invs; static void init(int n){ if(n+1<=(signed)fact.size()) return; fact.assign(n+1,1); finv.assign(n+1,1); invs.assign(n+1,1); for(int i=1;i<=n;i++) fact[i]=fact[i-1]*Mint(i); finv[n]=Mint(1)/fact[n]; for(int i=n;i>=1;i--) finv[i-1]=finv[i]*Mint(i); for(int i=1;i<=n;i++) invs[i]=finv[i]*fact[i-1]; } static Mint comb(long long n,int k){ Mint res(1); for(int i=0;i > D(int n,int m){ vector > dp(n+1,vector(m+1,0)); dp[0][0]=Mint(1); for(int i=0;i<=n;i++){ for(int j=1;j<=m;j++){ if(i-j>=0) dp[i][j]=dp[i][j-1]+dp[i-j][j]; else dp[i][j]=dp[i][j-1]; } } return dp; } static Mint B(int n,int k){ Mint res; for(int j=1;j<=k;j++) res+=S(n,j); return res; } static Mint montmort(int n){ Mint res; init(n); for(int k=2;k<=n;k++){ if(k&1) res-=finv[k]; else res+=finv[k]; } return res*=fact[n]; } static Mint LagrangePolynomial(vector &y,Mint t){ int n=y.size()-1; if(t.v<=n) return y[t.v]; init(n+1); Mint num(1); for(int i=0;i<=n;i++) num*=t-Mint(i); Mint res; for(int i=0;i<=n;i++){ Mint tmp=y[i]*num/(t-Mint(i))*finv[i]*finv[n-i]; if((n-i)&1) res-=tmp; else res+=tmp; } return res; } }; template vector > Mint::fact = vector >(); template vector > Mint::finv = vector >(); template vector > Mint::invs = vector >(); //INSERT ABOVE HERE signed main(){ int n; cin>>n; vector s(n),c(n); for(int i=0;i>s[i]; for(int i=0;i>c[i]; HLD hld(n); for(int i=1;i>a>>b; a--;b--; hld.add_edge(a,b); } hld.build(); using M = Mint; using T = pair; using E = M; auto f=[](T a,T b){return T(a.first+b.first,a.second+b.second);}; auto g=[](T a,E b){return T(a.first+a.second*b,a.second);}; auto h=[](E a,E b){return a+b;}; T ti(0,0); E ei(0); SegmentTree seg(f,g,h,ti,ei); vector vt(n); for(int i=0;i>q; for(int i=0;i>t; if(t==0){ int x,y,z; cin>>x>>y>>z; x--;y--; hld.for_each(x,y,[&](int l,int r){seg.update(l,r+1,z);}); } if(t==1){ int x,y; cin>>x>>y; x--;y--; M ans=0; hld.for_each(x,y,[&](int l,int r){ans+=seg.query(l,r+1).first;}); cout<