#line 1 "verify/yosupo/tree/hld/vertex_set_path_composite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite"
#line 2 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<class T>
using PQ = priority_queue<T,vector<T>,greater<T>>;
const int INF=INT_MAX/2;
const ll LINF=LLONG_MAX/4;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SZ(a) (int)(a.size())
#define SORT(a) sort(ALL(a))
#define RSORT(a) sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNI(a) a.erase(unique(ALL(a)),a.end())
#define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
#define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
#define FIND(a,x) (int)(find(ALL(a),x)-a.begin())
#define COUNT(a,x) (int)count(ALL(a),x)
#define MIN(a) *min_element(ALL(a))
#define MAX(a) *max_element(ALL(a))
template<class T,class U>
bool chmin(T &a,U b){return b<a?a=b,1:0;}
template<class T,class U>
bool chmax(T &a,U b){return a<b?a=b,1:0;}
template<class T>
T floor(T a,T b){return a/b-((a^b)<0&&a%b);}
template<class T>
T ceil(T a,T b){return a/b+((a^b)>=0&&a%b);}
int popcnt(ll x){return __builtin_popcountll(x);}
int topbit(ll x){return x==0?-1:63-__builtin_clzll(x);}
int lowbit(ll x){return x==0?-1:__builtin_ctzll(x);}
template<class T,class U>
T SUM(const U &a){return accumulate(ALL(a),T{});}
template<class T>
vector<int> argsort(const vector<T> &a){
vector<int> p(SZ(a));
iota(ALL(p),0);
stable_sort(ALL(p),[&](int i,int j){return a[i]<a[j];});
return p;
}
template<class T,size_t D=0>
struct VecBuilder{
array<size_t,D> d;
VecBuilder<T,D+1> operator[](size_t n)const{
VecBuilder<T,D+1> res{};
for(size_t i=0;i<D;i++)res.d[i]=d[i];
res.d[D]=n;
return res;
}
template<size_t I=0>
auto build(const T &x)const{
if constexpr(I+1==D)return vector<T>(d[I],x);
else return vector<decltype(build<I+1>(x))>(d[I],build<I+1>(x));
}
auto operator()(const T &x=T())const{
static_assert(D>0);
return build(x);
}
};
template<class T>
inline constexpr VecBuilder<T> VEC{};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "graph/graph-base.hpp"
/**
* Author: Teetat T.
* Date: 2024-06-15
* Description: Graph Base
*/
template<class T>
struct Edge{
int from,to,id;
T cost;
Edge(int _from,int _to,T _cost,int _id):from(_from),to(_to),cost(_cost),id(_id){}
operator int()const{return to;}
};
template<class T=void,bool directed=false>
struct Graph{
static constexpr bool is_directed=directed;
static constexpr bool is_weighted=!is_same<T,void>::value;
using cost_type = std::conditional_t<is_weighted,T,int>;
using edge_type = Edge<cost_type>;
int n,m;
vector<edge_type> edges;
vector<vector<edge_type>> g;
vector<int> _deg,_indeg,_outdeg;
Graph():n(0),m(0){}
Graph(int _n):n(_n),m(0),g(_n){}
vector<edge_type> &operator[](int u){return g[u];}
void add_edge(int from,int to,cost_type cost=1,int id=-1){
assert(0<=from&&from<n&&0<=to&&to<n);
if(id==-1)id=m;
edges.emplace_back(edge_type(from,to,cost,id));
g[from].emplace_back(edge_type(from,to,cost,id));
if(!is_directed)g[to].emplace_back(edge_type(to,from,cost,id));
m++;
}
void calc_deg(){
_deg.assign(n,0);
for(auto &e:edges)_deg[e.from]++,_deg[e.to]++;
}
void calc_inout_deg(){
_indeg.assign(n,0);
_outdeg.assign(n,0);
for(auto &e:edges)_outdeg[e.from]++,_indeg[e.to]++;
}
const vector<int> °_array(){
if(_deg.empty())calc_deg();
return _deg;
}
const vector<int> &indeg_array(){
if(_indeg.empty())calc_inout_deg();
return _indeg;
}
const vector<int> &outdeg_array(){
if(_outdeg.empty())calc_inout_deg();
return _outdeg;
}
int deg(int u){return deg_array()[u];}
int indeg(int u){return indeg_array()[u];}
int outdeg(int u){return outdeg_array()[u];}
Graph reverse(){
assert(is_directed);
Graph res(n);
for(auto &e:edges)res.add_edge(e.to,e.from,e.cost,e.id);
return res;
}
};
template<class T=void,bool directed=false>
Graph<T,directed> read_graph(int n,int m,int offset=1){
using G = Graph<T,directed>;
G g(n);
for(int i=0;i<m;i++){
int u,v;
cin >> u >> v;
u-=offset,v-=offset;
if(g.is_weighted){
typename G::cost_type w;
cin >> w;
g.add_edge(u,v,w);
}else{
g.add_edge(u,v);
}
}
return g;
}
template<class T=void,bool directed=false>
Graph<T,directed> read_tree(int n,int offset=1){
return read_graph<T,directed>(n,n-1,offset);
}
#line 2 "tree/hld.hpp"
/**
* Author: Teetat T.
* Date: 2024-06-15
* Description: Heavy-Light Decomposition.
*/
template<class G>
struct HLD{
int n;
G &g;
int root,timer;
vector<int> par,sz,dep,hv,head,tin,tout,ord;
HLD(G &_g,int _root=0)
: n(_g.n),g(_g),root(_root),timer(-1),par(n,root),sz(n,1),
dep(n),hv(n,-1),head(n),tin(n),tout(n),ord(n){
par[0]=-1;
dfs_sz(root);
dfs_hld(root);
}
void dfs_sz(int u){
for(int v:g[u])if(v!=par[u]){
par[v]=u;
dep[v]=dep[u]+1;
dfs_sz(v);
sz[u]+=sz[v];
if(hv[u]==-1||sz[v]>sz[hv[u]])hv[u]=v;
}
}
void dfs_hld(int u){
tin[u]=++timer;
ord[timer]=u;
if(hv[u]!=-1){
head[hv[u]]=head[u];
dfs_hld(hv[u]);
}
for(int v:g[u])if(v!=par[u]&&v!=hv[u]){
head[v]=v;
dfs_hld(v);
}
tout[u]=timer;
}
vector<pair<int,int>> get_path(int u,int v,bool vertex,bool commutative=true){
vector<pair<int,int>> up,down;
while(head[u]!=head[v]){
if(dep[head[u]]>dep[head[v]]){
up.emplace_back(tin[head[u]],tin[u]);
u=par[head[u]];
}else{
down.emplace_back(tin[head[v]],tin[v]);
v=par[head[v]];
}
}
if(dep[u]>dep[v])up.emplace_back(tin[v]+1,tin[u]),u=v;
else if(u!=v)down.emplace_back(tin[u]+1,tin[v]),v=u;
if(vertex)up.emplace_back(tin[u],tin[u]);
reverse(down.begin(),down.end());
if(!commutative)for(auto &[x,y]:up)swap(x,y);
up.insert(up.end(),down.begin(),down.end());
return up;
}
int lca(int u,int v){
while(head[u]!=head[v]){
if(dep[head[u]]>dep[head[v]])swap(u,v);
v=par[head[v]];
}
return dep[u]<dep[v]?u:v;
}
int dist(int u,int v){
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
int jump(int u,int v,int k){
int w=lca(u,v);
int d=dep[u]+dep[v]-2*dep[w];
if(k>d)return -1;
if(k>dep[u]-dep[w]){
k=d-k;
swap(u,v);
}
while(k>=dep[u]-dep[head[u]]+1){
k-=dep[u]-dep[head[u]]+1;
u=par[head[u]];
}
return ord[tin[u]-k];
}
bool is_ancestor(int u,int v){
return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
};
#line 2 "group/monoid/affine.hpp"
/**
* Author: Teetat T.
* Date: 2024-04-14
* Description: Affine Transformation Monoid class.
*/
template<class T>
struct AffineMonoid{
using P = pair<T,T>;
using value_type = P;
static constexpr P op(const P &x,const P &y){
return P(x.first*y.first,x.second*y.first+y.second);
}
static constexpr P unit(){return P(T(1),T(0));}
static constexpr T eval(const P &f,const T &x){
return f.first*x+f.second;
}
};
#line 2 "group/monoid/monoid-reverse.hpp"
/**
* Author: Teetat T.
* Date: 2024-06-16
* Description: Monoid Reverse class.
*/
template<class Monoid>
struct MonoidReverse{
using value_type = typename Monoid::value_type;
static constexpr value_type op(const value_type &x,const value_type &y){return Monoid::op(y,x);}
static constexpr value_type unit(){return Monoid::unit();}
};
#line 2 "modular-arithmetic/modint.hpp"
/**
* Author: Teetat T.
* Date: 2026-04-15
* Description: modular arithmetic operations
*/
template<int mod,int root=0>
struct ModInt{
using mint = ModInt;
static_assert(mod>0,"mod must be positive");
int x;
constexpr ModInt():x(0){}
constexpr ModInt(ll x):x((x%=mod)<0?x+mod:x){}
constexpr explicit operator int()const{return x;}
constexpr int val()const{return x;}
constexpr static int get_mod(){return mod;}
constexpr static mint get_root(){return mint(root);}
constexpr mint operator-()const{
mint res;
res.x=x?mod-x:0;
return res;
}
constexpr mint operator+()const{return *this;}
constexpr mint inv()const{
int a=x,b=mod,u=1,v=0,q=0;
while(b>0){
q=a/b;
swap(a-=q*b,b);
swap(u-=q*v,v);
}
return mint(u);
}
constexpr mint pow(ll n)const{
mint res=1,a=*this;
for(;n>0;a*=a,n>>=1)if(n&1)res*=a;
return res;
}
constexpr mint &operator+=(const mint &o){
if((x+=o.x)>=mod)x-=mod;
return *this;
}
constexpr mint &operator-=(const mint &o){
if((x-=o.x)<0)x+=mod;
return *this;
}
constexpr mint &operator*=(const mint &o){
x=(ll(x)*o.x)%mod;
return *this;
}
constexpr mint &operator/=(const mint &o){
return *this*=o.inv();
}
constexpr mint operator+(const mint &o)const{return mint(*this)+=o;}
constexpr mint operator-(const mint &o)const{return mint(*this)-=o;}
constexpr mint operator*(const mint &o)const{return mint(*this)*=o;}
constexpr mint operator/(const mint &o)const{return mint(*this)/=o;}
constexpr mint &operator++(){return *this+=mint(1);}
constexpr mint &operator--(){return *this-=mint(1);}
constexpr mint operator++(int){mint res=*this;*this+=mint(1);return res;}
constexpr mint operator--(int){mint res=*this;*this-=mint(1);return res;}
constexpr bool operator==(const mint &o)const{return x==o.x;}
constexpr bool operator!=(const mint &o)const{return x!=o.x;}
constexpr bool operator<(const mint &o)const{return x<o.x;}
friend istream &operator>>(istream &is,mint &o){ll x{};is>>x;o=mint(x);return is;}
friend ostream &operator<<(ostream &os,const mint &o){return os<<o.x;}
};
using mint998 = ModInt<998244353,3>;
using mint107 = ModInt<1000000007>;
#line 2 "data-structure/segment-tree/segment-tree.hpp"
/**
* Author: Teetat T.
* Date: 2024-01-15
* Description: Segment Tree
*/
template<class Monoid>
struct SegmentTree{
using T = typename Monoid::value_type;
int n;
vector<T> t;
SegmentTree(){}
SegmentTree(int n,function<T(int)> create){init(n,create);}
SegmentTree(int n,T v=Monoid::unit()){init(n,[&](int){return v;});}
template<class U>
SegmentTree(const vector<U> &a){init((int)a.size(),[&](int i){return T(a[i]);});}
void init(int _n,function<T(int)> create){
n=_n;
t.assign(4<<(31-__builtin_clz(n)),Monoid::unit());
function<void(int,int,int)> build=[&](int l,int r,int i){
if(l==r)return void(t[i]=create(l));
int m=(l+r)/2;
build(l,m,i*2);
build(m+1,r,i*2+1);
pull(i);
};
build(0,n-1,1);
}
void pull(int i){
t[i]=Monoid::op(t[i*2],t[i*2+1]);
}
void modify(int l,int r,int i,int x,const T &v){
if(x<l||r<x)return;
if(l==r)return void(t[i]=v);
int m=(l+r)/2;
modify(l,m,i*2,x,v);
modify(m+1,r,i*2+1,x,v);
pull(i);
}
void modify(int x,const T &v){
modify(0,n-1,1,x,v);
}
template<class U>
void update(int l,int r,int i,int x,const U &v){
if(x<l||r<x)return;
if(l==r)return void(t[i]=Monoid::op(t[i],v));
int m=(l+r)/2;
update(l,m,i*2,x,v);
update(m+1,r,i*2+1,x,v);
pull(i);
}
template<class U>
void update(int x,const U &v){
update(0,n-1,1,x,v);
}
T query(int l,int r,int i,int x,int y){
if(y<l||r<x)return Monoid::unit();
if(x<=l&&r<=y)return t[i];
int m=(l+r)/2;
return Monoid::op(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
}
T query(int x,int y){
return query(0,n-1,1,x,y);
}
template<class F>
int findfirst(int l,int r,int i,int x,int y,const F &f){
if(y<l||r<x||!f(t[i]))return n;
if(l==r)return l;
int m=(l+r)/2;
int res=findfirst(l,m,i*2,x,y,f);
if(res==n)res=findfirst(m+1,r,i*2+1,x,y,f);
return res;
}
template<class F>
int findfirst(int x,int y,const F &f){
return findfirst(0,n-1,1,x,y,f);
}
template<class F>
int findlast(int l,int r,int i,int x,int y,const F &f){
if(y<l||r<x||!f(t[i]))return -1;
if(l==r)return l;
int m=(l+r)/2;
int res=findlast(m+1,r,i*2+1,x,y,f);
if(res==-1)res=findlast(l,m,i*2,x,y,f);
return res;
}
template<class F>
int findlast(int x,int y,const F &f){
return findlast(0,n-1,1,x,y,f);
}
};
#line 9 "verify/yosupo/tree/hld/vertex_set_path_composite.test.cpp"
using mint = mint998;
using Mon = AffineMonoid<mint>;
using Rev = MonoidReverse<Mon>;
using T = Mon::value_type;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,q;
cin >> n >> q;
vector<T> a(n);
for(auto &[x,y]:a)cin >> x >> y;
auto g=read_tree(n,0);
HLD hld(g);
auto b=a;
for(int i=0;i<n;i++)a[hld.tin[i]]=b[i];
SegmentTree<Mon> s(a);
SegmentTree<Rev> sr(a);
while(q--){
int op;
cin >> op;
if(op==0){
int p;
mint x,y;
cin >> p >> x >> y;
s.modify(hld.tin[p],T(x,y));
sr.modify(hld.tin[p],T(x,y));
}else{
int u,v;
cin >> u >> v;
mint x;
cin >> x;
for(auto [u,v]:hld.get_path(u,v,true,false)){
if(u<=v){
x=Mon::eval(s.query(u,v),x);
}else{
x=Mon::eval(sr.query(v,u),x);
}
}
cout << x << "\n";
}
}
}
verify/yosupo/tree/hld/vertex_set_path_composite.test.cpp