记录，RE on #6 and AC on #11，其余 TLE。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define ull unsigned int
#define pb push_back
#define pii pair<int,int>
#define p3i pair<int,pii>
#define uset unordered_set
#define umap unordered_map
#define prq priority_queue
#define fi first
#define se second
#define ctn continue
#define N 100005
int n,T,rt,mod,a[N];
vector<int>e[N];
struct heavy_path_decomposition	//重链剖分 
{
	//decomposition (n.) 分解 
	int tot=0,dep[N],fa[N],siz[N],son[N],dfn[N],rnk[N],top[N];
	void dfs1(int u)
	{
		dep[u]=dep[fa[u]]+1;
		siz[u]=1;
		for(int v:e[u])
		{
			if(v^fa[u])
			{
				fa[v]=u;
				dfs1(v);
				siz[u]+=siz[v];
				if(!son[u] || siz[v]>siz[son[u]])
				{
					son[u]=v;
				}
			}
		}
	}
	void dfs2(int u,int t)
	{
		dfn[u]=++tot;
		rnk[tot]=u;
		top[u]=t;
//		cout<<"u="<<u<<"  t="<<t<<"  tot="<<tot<<"  dfn[u]="<<dfn[u]<<"  rnk[tot]="<<rnk[tot]<<"  top[u]="<<top[u]<<"\n";
		if(!son[u])
		{
			return;
		}
		dfs2(son[u],t);
		for(int v:e[u])
		{
			if(v^fa[u] && v^son[u])
			{
				dfs2(v,v);
			}
		}
	}
	int lca(int x,int y)
	{
		while(top[x]^top[y])
		{
			if(dep[top[x]]<dep[top[y]])
			{
				swap(x,y);
			}
			x=fa[top[x]];
		}
		return dep[x]<dep[y] ? x : y;
	}
}hpd;
struct segment_tree	//线段树 
{
	struct node
	{
		int l,r,val,tag;
		node(int _l=0,int _r=0,int _val=0,int _tag=0)
		{
			l=_l, r=_r, val=_val, tag=_tag;
		}
	}t[N<<2];
	void build(int p,int l,int r)
	{
		if(l==r)
		{
			t[p]=node(l,r,a[hpd.rnk[l]]%mod,0);
//			cout<<"t["<<p<<"]={"<<l<<","<<r<<","<<a[hpd.rnk[l]]%mod<<",0}\n";
			return;
		}
		int mid=(l+r)>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		t[p]=node(l, r, (t[p<<1].val+t[p<<1|1].val)%mod, 0);
	}
	void push_down(int p)
	{
		if(t[p].tag)
		{
			t[p<<1].tag+=t[p].tag;
			t[p<<1].tag%=mod;
			t[p<<1].val+=(t[p<<1].r-t[p<<1].l+1)*t[p].tag;
			t[p<<1].val%=mod;
			t[p<<1|1].tag+=t[p].tag;
			t[p<<1|1].tag%=mod;
			t[p<<1|1].val+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].tag;
			t[p<<1|1].val%=mod;
			t[p].tag=0;
		}
	}
	int query(int p,int l,int r)
	{
		if(t[p].r<l || t[p].l>r)
		{
			return 0;
		}
		if(t[p].l>=l && t[p].r<=r)
		{
			return t[p].val%mod;
		}
		push_down(p);
		return ( query(p<<1,l,r) + query(p<<1|1,l,r) ) % mod;
	}
	void add(int p,int l,int r,int k)
	{
		int pl=t[p].l, pr=t[p].r;
		if(pr<l || pl>r)
		{
			return;
		}
		t[p].val+=(min(pr,r)-max(pl,l)+1)*k;
		t[p].val%=mod;
		if(pl>=l && pr<=r)
		{
			t[p].tag+=k;
			t[p].tag%=mod;
			return;
		}
		push_down(p);
		add(p<<1,l,r,k);
		add(p<<1|1,l,r,k);
	}
}seg;
int add_path(int x,int y,int z)
{
	z%=mod;
//	cout<<"x="<<x<<"  y="<<y<<"  top[x]="<<hpd.top[x]<<"  top[y]="<<hpd.top[y]<<"\n";
	while(hpd.top[x]^hpd.top[y])
	{
//		cout<<"(top[x] != top[y])  x="<<x<<"  y="<<y<<"  top[x]="<<hpd.top[x]<<"  top[y]="<<hpd.top[y]<<"\n";
		if(hpd.dep[ hpd.top[x] ] < hpd.dep[ hpd.top[y] ])
		{
			swap(x,y);
		}
		seg.add(1, hpd.dfn[ hpd.top[x] ], hpd.dfn[x], z);
//		cout<<"add(1,"<<hpd.dfn[ hpd.top[x] ]<<","<<hpd.dfn[x]<<","<<z<<")\n";
		x = hpd.fa[ hpd.top[x] ];
	}
	if(hpd.dep[x] > hpd.dep[y])
	{
		swap(x,y);
	}
	seg.add(1, hpd.dfn[x], hpd.dfn[y], z);
}
int query_path(int x,int y)
{
	int ret=0;
	while(hpd.top[x]^hpd.top[y])
	{
		if(hpd.dep[ hpd.top[x] ] < hpd.dep[ hpd.top[y] ])
		{
			swap(x,y);
		}
		ret+=seg.query(1, hpd.dfn[ hpd.top[x] ], hpd.dfn[x]);
		ret%=mod;
		x = hpd.fa[ hpd.top[x] ];
	}
	if(hpd.dep[x] > hpd.dep[y])
	{
		swap(x,y);
	}
	ret+=seg.query(1, hpd.dfn[x], hpd.dfn[y]);
	ret%=mod;
	return ret;
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	cin>>n>>T>>rt>>mod;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1,u,v;i<n;i++)
	{
		cin>>u>>v;
		e[u].pb(v);
		e[v].pb(u);
	}
	hpd.dfs1(rt);
	hpd.dfs2(rt,rt);
	seg.build(1,1,n);
	while(T--)
	{
		int op,x,y,z;
		cin>>op>>x;
		if(op==1)
		{
			cin>>y>>z;
			z=(z%mod+mod)%mod;
			add_path(x,y,z);
		}
		else if(op==2)
		{
			cin>>y;
			cout<<query_path(x,y)<<"\n";
		}
		else if(op==3)
		{
			cin>>z;
			z=(z%mod+mod)%mod;
			seg.add(1, hpd.dfn[x], hpd.dfn[x]+hpd.siz[x]-1, z);
		}
		else
		{
			cout<<seg.query(1, hpd.dfn[x], hpd.dfn[x]+hpd.siz[x]-1)<<"\n";
		}
	}
	return 0;
}