#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 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 struct LinkCutTree{ struct Node{ Node *l,*r,*p; size_t sz;// tree size (only for root) int idx; bool rev; T val,dat; E laz; Node():sz(1){} Node(int idx,T val,E laz): sz(1),idx(idx),rev(0),val(val),dat(val),laz(laz){l=r=p=nullptr;} bool is_root(){ return !p||(p->l!=this&&p->r!=this); } }; using F = function; using G = function; using H = function; using S = function; F f; G g; H h; S s; T ti; E ei; const size_t LIM = 1e6; vector pool; size_t ptr; LinkCutTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei),pool(LIM),ptr(0){ s=[](T a){return a;}; } LinkCutTree(F f,G g,H h,S s,T ti,E ei): f(f),g(g),h(h),s(s),ti(ti),ei(ei),pool(LIM),ptr(0){} inline Node* create(){ return &pool[ptr++]; } inline Node* create(int idx,T v){ return &(pool[ptr++]=Node(idx,v,ei)); } void propagate(Node *t,E v){ t->laz=h(t->laz,v); t->val=g(t->val,v); t->dat=g(t->dat,v); } void toggle(Node *t){ swap(t->l,t->r); t->dat=s(t->dat); t->rev^=1; } void eval(Node *t){ if(t->laz!=ei){ if(t->l) propagate(t->l,t->laz); if(t->r) propagate(t->r,t->laz); t->laz=ei; } if(t->rev){ if(t->l) toggle(t->l); if(t->r) toggle(t->r); t->rev=false; } } void recalc(Node *t){ t->dat=t->val; if(t->l) t->dat=f(t->l->dat,t->dat); if(t->r) t->dat=f(t->dat,t->r->dat); } void rotR(Node *t){ Node *x=t->p,*y=x->p; x->sz-=t->sz; t->sz+=x->sz; if((x->l=t->r)) t->r->p=x,x->sz+=x->l->sz; t->r=x;x->p=t; recalc(x);recalc(t); if((t->p=y)){ if(y->l==x) y->l=t; if(y->r==x) y->r=t; recalc(y); } } void rotL(Node *t){ Node *x=t->p,*y=x->p; x->sz-=t->sz; t->sz+=x->sz; if((x->r=t->l)) t->l->p=x,x->sz+=x->r->sz; t->l=x;x->p=t; recalc(x);recalc(t); if((t->p=y)){ if(y->l==x) y->l=t; if(y->r==x) y->r=t; recalc(y); } } void splay(Node *t){ eval(t); while(!t->is_root()){ Node *q=t->p; if(q->is_root()){ eval(q);eval(t); if(q->l==t) rotR(t); else rotL(t); }else{ auto *r=q->p; eval(r);eval(q);eval(t); if(r->l==q){ if(q->l==t) rotR(q),rotR(t); else rotL(t),rotR(t); }else{ if(q->r==t) rotL(q),rotL(t); else rotR(t),rotL(t); } } } } Node* expose(Node *t){ Node *rp=nullptr; for(Node *c=t;c;c=c->p){ splay(c); c->r=rp; recalc(c); rp=c; } splay(t); return rp; } void link(Node *par,Node *c){ expose(c); expose(par); c->p=par; par->r=c; par->sz+=c->sz; } void cut(Node *c){ expose(c); Node *par=c->l; c->l=nullptr; par->p=nullptr; c->sz-=par->sz; } void evert(Node *t){ expose(t); toggle(t); eval(t); } bool is_connected(Node *a,Node *b){ expose(a); while(a->l) a=a->l; expose(b); while(b->l) b=b->l; return expose(a)==expose(b); } Node *lca(Node *a,Node *b){ expose(a); return expose(b); } T query(Node *t){ expose(t); return t->dat; } void update(Node *t,E v){ expose(t); propagate(t,v); eval(t); } }; //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]; vector > G(n); for(int i=1;i>a>>b; a--;b--; G[a].emplace_back(b); G[b].emplace_back(a); } 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); using LCT = LinkCutTree; LCT lct(f,g,h,ti,ei); vector vs(n); for(int i=0;i dfs= [&](int v,int p){ for(int u:G[v]){ if(u==p) continue; dfs(u,v); lct.link(vs[v],vs[u]); } }; dfs(0,-1); int q; cin>>q; for(int i=0;i>t; if(t==0){ int x,y,z; cin>>x>>y>>z; x--;y--; lct.evert(vs[x]); lct.update(vs[y],M(z)); } if(t==1){ int x,y; cin>>x>>y; x--;y--; lct.evert(vs[x]); cout<