$rt$，$NOIP$ 考前复习板子，树剖 $73\ pts$ 挂 $on$ #8，#9，#10。

要考 $NOIP$ 了，急，玄关。

开了 long long 并没有什么卵用。

//【模板】树链剖分 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
inline void read(int &n){
	int s=0,t=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') t=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);c=getchar();
	}
	n=s*t;
}
inline void put(int n){
	if(n<0){
		putchar('-');n=-n;
	}
	if(n<10){
		putchar(n+48);return;
	}
	put(n/10);
	putchar(n%10+48);
}
struct node{
	int v,nxt;
}e[MAXN<<1];
struct sgt{
	int l,r,sum,tag;
}t[MAXN<<1];
int n,p,root,tot,cnt,tal,a[MAXN],b[MAXN],head[MAXN],dep[MAXN],siz[MAXN],fa[MAXN],son[MAXN],id[MAXN],top[MAXN];
inline void add(int u,int v){
	++tot;
	e[tot].v=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}
inline void dfs1(int u,int f){
	fa[u]=f;dep[u]=dep[f]+1;siz[u]=1;
	for(register int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v!=f){
			dfs1(v,u);siz[u]+=siz[v];
			if(siz[v]>siz[son[u]]) son[u]=v;
		}
	}
}
inline void dfs2(int u,int ltop){
	id[u]=++cnt;b[cnt]=a[u];top[u]=ltop;
	if(son[u]) dfs2(son[u],ltop);
	for(register int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
	}
}
inline void pushup(int rt){
	t[rt].sum=(t[t[rt].l].sum+t[t[rt].r].sum)%p;
}
inline void pushdown(int rt,int l,int r){
	if(t[rt].tag){
		int mid=(l+r)>>1;
		t[t[rt].l].sum=(t[t[rt].l].sum+(mid-l+1)*t[rt].tag)%p;
		t[t[rt].r].sum=(t[t[rt].r].sum+(r-mid)*t[rt].tag)%p;
		t[t[rt].l].tag=(t[t[rt].l].tag+t[rt].tag)%p;
		t[t[rt].r].tag=(t[t[rt].r].tag+t[rt].tag)%p;
		t[rt].tag=0;
	}
}
inline void build(int &rt,int l,int r){
	if(!rt) rt=++tot;
	if(l==r){
		t[tot].sum=b[l]%p;return;
	}
	int mid=(l+r)>>1;
	build(t[rt].l,l,mid);build(t[rt].r,mid+1,r);
	pushup(rt);
}
inline void update(int rt,int l,int r,int left,int right,int x){
	if(l>=left&&r<=right){
		t[rt].sum=(t[rt].sum+(r-l+1)*x)%p;t[rt].tag=(t[rt].tag+x)%p;return;
	}
	pushdown(rt,l,r);
	int mid=(l+r)>>1;
	if(left<=mid) update(t[rt].l,l,mid,left,right,x);
	if(right>mid) update(t[rt].r,mid+1,r,left,right,x);
	pushup(rt);
}
inline int query(int rt,int l,int r,int left,int right){
	if(l>=left&&r<=right) return t[rt].sum;
	pushdown(rt,l,r);
	int mid=(l+r)>>1,ans=0;
	if(left<=mid) ans=(ans+query(t[rt].l,l,mid,left,right))%p;
	if(right>mid) ans=(ans+query(t[rt].r,mid+1,r,left,right))%p;
	return ans;
}
inline void range(int x,int y,int z){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]) swap(x,y);
		update(root,1,n,id[top[y]],id[y],z);y=fa[top[y]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	update(root,1,n,id[x],id[y],z);
}
inline int getsum(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]) swap(x,y);
		ans=(ans+query(root,1,n,id[top[y]],id[y]))%p;y=fa[top[y]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans=(ans+query(root,1,n,id[x],id[y]))%p;
	return ans;
}
int main(){
	int m,r,opt,x,y,z;
	read(n);read(m);read(r);read(p);
	for(register int i=1;i<=n;++i) read(a[i]);
	for(register int i=1;i<n;++i){
		read(x);read(y);add(x,y);add(y,x);
	}
	dfs1(r,0);dfs2(r,r);build(root,1,n);
	for(register int i=1;i<=m;++i){
		read(opt);read(x);
		if(opt==1){
			read(y);read(z);range(x,y,z%p);
		}
		else if(opt==2){
			read(y);put(getsum(x,y));putchar('\n');
		}
		else if(opt==3){
			read(z);update(root,1,n,id[x],id[x]+siz[x]-1,z%p);
		}
		else{
			put(query(root,1,n,id[x],id[x]+siz[x]-1));putchar('\n');
		}
	}
	return 0;
}