Beautiful Tree

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod=998244353;
const int N=5*1e5+7;
vector<int> beauty;
vector<vector<int>> e;
vector<int> a,seg,val;
vector<int> in,out;
int n,q,Size;
ll x;
/*----------------------------------------------Debug start------------------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*------------------------------------------------------Debug End------------------------------------------------------*/
// Fucntion to calculate ith beautiful value
void preprocess()
{
    queue<pair<int,ll>> q;
    q.push(make_pair(0,0ll));
    while((int)beauty.size()<N)
    {
        auto t=q.front(); q.pop();
        beauty.emplace_back(t.first);
        for(int i=0;i<10;i++)
        {
            if(i==0 && t.first==0) continue;
            if(t.second+i*i<=x)
                q.push({(t.first*10+i)%mod,t.second+i*i});
        }
    }
}
int Time;
//conduct a euler tour using dfs
void dfs(int s,int p=-1)
{
    in[s]=Time++;
    a.emplace_back(s);
    for(int i:e[s])
    {
        if(i!=p)
            dfs(i,s);
    }
    a.emplace_back(s);
    out[s]=Time++;
}
void build()
{
    Size=1;
    while(Size<(int)a.size()) Size*=2;
    Size=2*Size-1;
    seg=vector<int>(Size,0);
    for(size_t i=0;i<a.size();i++)
        seg[i+Size/2]=beauty[val[a[i]]];
    for(int i=Size/2-1;i>=0;i--)
        seg[i]=(seg[2*i+1]+seg[2*i+2])%mod;
}
void Set(int index,int val)
{
    index+=Size/2;
    seg[index]=beauty[val];
    int pos=(index-1)/2;
    while(pos>=0)
    {
        seg[pos]=(seg[2*pos+1]+seg[2*pos+2])%mod;
        if(pos==0)pos=-1;
        else pos=(pos-1)/2;
    }
    debug(seg);
}
int get(int left,int right)
{
    int sum=0;
    left+=Size/2,right+=Size/2;
    while(left<right)
    {
        debug(left,right);
        if(right&1) sum=(sum+seg[right--])%mod;
        right=(right-1)/2;
        if(!(left&1)) sum=(sum+seg[left++])%mod;
        left=(left-1)/2;
    }
    if(left==right) sum=(sum+seg[left])%mod;
    return sum;
}
int sum(int root)
{
    int val=get(in[root],out[root])/2;
    cerr<<"here\n";
    return val;
}
void update(int pos,int ne)
{
    Set(in[pos],ne);
    Set(out[pos],ne);
}
int main()
{
    /*ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);*/
    cin>>n>>q>>x;
    e=vector<vector<int>>(n);
    in.resize(n); out.resize(n);
    val.resize(n);
    preprocess();
    for(int i=0;i<n-1;i++)
    {
        int u,v; cin>>u>>v;
        e[u-1].emplace_back(v-1);
        e[v-1].emplace_back(u-1);
    }
    for(int i=0;i<n;i++)
        cin>>val[i];
    Time=0;
    dfs(0);
    build();
    debug(seg);
    while(q--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int pos,ne;
            cin>>pos>>ne;
            update(pos-1,ne);
        }
        else
        {
            int root=0;
            cin>>root;
            int val=sum(root-1);
            debug(val);
            cout<<val<<"\n";
        }
    }
    return 0;
}