#include <bits/stdc++.h>
#define I using
#define AK namespace
#define CSP std
#define reg register
I AK CSP;
typedef long long ll;
const int M=1e5+9;
ll n,q,root,p;
ll a[M];
vector<ll>gr[M];
ll dfn[M],siz[M],dep[M],todfn[M],top[M],fa[M],hson[M],tr[M],islz[M];
ll idx=0;
void BuildWeight(int x,int f){
	cout<<x<<' '<<f<<'\n';
	fa[x]=f;
	siz[x]=1;
	dep[x]=dep[f]+1;
	for(ll it:gr[x]){
		if(it==f)continue;
		BuildWeight(it,x);
		siz[x]+=siz[it];
		if(siz[hson[x]]<=siz[it])hson[x]=it;
	}
}
void FindLink(int x,int tp){
	cout<<x<<' '<<tp<<'\n';
	top[x]=tp;
	todfn[++idx]=x;
	dfn[x]=idx;
	if(hson[x])FindLink(hson[x],tp);
	else return ;
	for(ll it:gr[x]){
		if(it==hson[x]||it==fa[x])continue;
		FindLink(it,it);
	}
}
void push_up(ll i){
	tr[i]=(tr[i*2]+tr[(i*2)+1])%p;
}
void BuildTree(ll i,ll l,ll r){
	if(l>r)return ;
	if(l==r){
		tr[i]=a[todfn[l]]%p;
		return;
	}
	BuildTree(i*2,l,(l+r)/2);
	BuildTree((i*2)+1,(l+r)/2+1,r);
	push_up(i);
}
void push_down(ll i,ll l,ll r){
	if(islz[i]){
		tr[i*2]+=islz[i*2]%p*(((l+r)/2)-l+1)%p;
		tr[(i*2)+1]+=islz[(i*2)+1]%p*(r-((l+r)/2+1)+1)%p;
		islz[i*2]=islz[i];
		islz[(i*2)+1]=islz[i];
		islz[i]=0;
	}
}
void update(ll l,ll r,ll x);
ll get(ll l,ll r);
void add(ll pos,ll l,ll r,ll al,ll ar,ll x);
ll query(ll pos,ll l,ll r,ll al,ll ar);
int main(){
	scanf("%lld%lld%lld%lld",&n,&q,&root,&p);
	for(reg int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(reg int i=1;i<n;i++){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		gr[x].push_back(y);
		gr[y].push_back(x);
	}
	BuildWeight(root,0);
	FindLink(root,root);
	BuildTree(1,1,n);
	for(int i=1;i<=n;i++){
		cout<<dfn[i]<<' ';
	}
	puts("");
	while(q--){
		int opt,x,y,z;
		scanf("%d",&opt);
        cout<<opt;
        puts("");
		if(opt==1){
			scanf("%d%d%d",&x,&y,&z); 
			update(x,y,z);
		}
		if(opt==2){
			scanf("%d%d",&x,&y);
			cout<<get(x,y);
			puts("");
		}
		if(opt==3){
			scanf("%d%d",&x,&y);
			add(1,1,n,dfn[x],dfn[x]+siz[x]-1,z);
		}
		if(opt==4){
			scanf("%d",&x);
			cout<<query(1,1,n,dfn[x],dfn[x]+siz[x]-1);
			puts("");
		}
        puts("");
	}
	return 0;
}
void update(ll l,ll r,ll x){
	while(top[l]!=top[r]){
        cout<<l<<' '<<r<<'\n';
		if(dep[top[l]]<dep[top[r]])swap(l,r);
		add(1,1,n,dfn[top[l]],dfn[l],x);
		l=fa[top[l]];
	}
	if(dep[l]<dep[r])swap(l,r);
	add(1,1,n,dfn[r],dfn[l],x);
}
ll get(ll l,ll r){
    ll ans=0;
	while(top[l]!=top[r]){
        cout<<l<<' '<<r<<'\n';
		if(dep[top[l]]<dep[top[r]])swap(l,r);
		ans=(ans+query(1,1,n,dfn[top[l]],dfn[l]))%p;
		cout<<ans<<'\n';
		l=fa[top[l]];
	}
	if(dep[l]<dep[r])swap(l,r);
	ans+=query(1,1,n,dfn[r],dfn[l]);
	ans%=p;
	return ans%p;
}
void add(ll pos,ll l,ll r,ll al,ll ar,ll x){
    cout<<l<<' '<<r<<'\n';
	if(l>r)return ;
	if(l>ar||r<al)return;
	if(l>=al&&r<=ar){
		tr[pos]+=x%p*(r-l+1)%p;
		tr[pos]%=p;
		islz[pos]+=x;
		islz[pos]%=p;
		return ;
	}
	push_down(pos,l,r);
	add(pos*2,l,(l+r)/2,al,ar,x);
	add(pos*2,((l+r)/2)+1,r,al,ar,x);
	push_up(pos);
}
ll query(ll pos,ll l,ll r,ll al,ll ar){
    cout<<l<<' '<<r<<'\n';
	if(l>r)return 0;
	if(l>ar||r<al)return 0;
	if(l>=al&&r<=ar){
		return tr[pos]%p;
	}
	ll ans=0;
	push_down(pos,l,r);
	ans+=query(pos*2,l,(l+r)/2,al,ar);
	ans%=p;
	ans+=query((pos*2)+1,((l+r)/2)+1,r,al,ar);
	ans%=p;
	push_up(pos);
	return ans%p;
}

        

样例WA