#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node{
	int ch[2],fa,val,cnt;
	int size;
}tree[N];
int n,m,root,tot;
void pushup(int x){
	if(!x)return;
	tree[x].size = tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+tree[x].cnt;
}
int Get(int x){
	//返回x为左儿子还是右儿子
	return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
	int y = tree[x].fa,z=tree[y].fa,chk=Get(x);
	tree[y].ch[chk] = tree[x].ch[chk^1];
	if(tree[x].ch[chk^1]) tree[tree[x].ch[chk^1]].fa = y;
	tree[x].ch[chk^1] = y;
	tree[y].fa = x;
	if(z)tree[z].ch[y==tree[z].ch[1]] = x;
	tree[x].fa = z;
	pushup(y);
	pushup(x);
}
void splay(int x,int k){
	while(tree[x].fa!=k){
		int y = tree[x].fa,z=tree[y].fa;
		if(z!=k){
			if(Get(x)==Get(y))rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if(k==0)root = x;
}
void insert(int x){
	int cur = root;
	int fa = 0;
	while(cur){
		if(tree[cur].val == x){
			tree[cur].cnt++;
			pushup(cur);
			pushup(fa);
			splay(cur,0);
			return;
		}
		fa = cur;
		cur = tree[cur].ch[x>tree[cur].val];
	}
	cur = ++tot;
	tree[cur].val = x;
	tree[cur].cnt = 1;
	tree[cur].fa = fa;
	tree[fa].ch[x>tree[fa].val] = cur;
	pushup(cur);
	pushup(fa);
	splay(cur,0);
	return;
}
int rnk(int x){
	int cur = root;
	int res = 0;
	while(cur){
		if(x<tree[cur].val){
			cur = tree[cur].ch[0];
		}
		else{
			res+=tree[tree[cur].ch[0]].size;
			if(x==tree[cur].val){
				splay(cur,0);
				return res+1;
			}
			else{
				res+=tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return res+1;
}
int kth(int x){
	//查询排名为x 的数
	int cur = root;
	while(cur){
		if(x<=tree[tree[cur].ch[0]].size){
			cur = tree[cur].ch[0];
		}
		else{
			x-=tree[tree[cur].ch[0]].size;
			if(x<=tree[cur].cnt){
				splay(cur,0);
				return cur;
			}
			else{
				x-=tree[cur].cnt;
				cur = tree[cur].ch[1];
			}
		}
	}
	return -1;
}
int pre(int x){
	//查询比x小的最大值
	int cur=root;
	int res = -1e9;
	while(cur){
		if(x>tree[cur].val){
			res = max(res,tree[cur].val);
			cur = tree[cur].ch[1];
		}
		else{
			cur = tree[cur].ch[0];
		}
	}
	return res;
}
int nxt(int x){
	int cur = root;
	int res = 1e9;
	while(cur){
		if(x<tree[cur].val){
			res = min(res,tree[cur].val);
			cur = tree[cur].ch[0];
		}
		else cur = tree[cur].ch[1];
	}
	return res;
}
void find(int x){
	int cur = root;
	while(cur){
		if(x==tree[cur].val){
			splay(cur,0);
			return;
		}
		cur = tree[cur].ch[x>tree[cur].val];
	}
}
void del(int x){
	find(x);
	int L = tree[root].ch[0],R=tree[root].ch[1];
	while(tree[L].ch[1])L=tree[L].ch[1];
	while(tree[R].ch[0])R=tree[R].ch[0];
	splay(L,0);
	splay(R,L);
	if(tree[tree[R].ch[0]].cnt>1){
		tree[tree[R].ch[0]].cnt--;
		pushup(tree[R].ch[0]);
		pushup(R);
		pushup(L);
	}
	else{
		tree[R].ch[0] = 0;
		pushup(R);
		pushup(L);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	insert(-1e9);
	insert(1e9);
	cin>>n;
	for(int i=1;i<=n;i++){
		int op,x;
		cin>>op>>x;
		if(op==1){
			insert(x);
		}
		else if(op==2){
			del(x);
		}
		else if(op==3){
			cout<<rnk(x)-1<<'\n';
		}
		else if(op==4){
			cout<<tree[kth(x+1)].val<<'\n';
		}
		else if(op==5){
			cout<<pre(x)<<'\n';
		}
		else if(op==6){
			cout<<nxt(x)<<'\n';
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node{
	int ch[2],fa,val;
	int size,rev;
}tree[N];
int n,m,root,tot;
void pushup(int x){
	if(!x)return;
	tree[x].size = tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1;
}
void pushrev(int x){
	tree[x].rev^=1;
	swap(tree[x].ch[0],tree[x].ch[1]);
}
void pushdown(int x){
	if(tree[x].rev){
		pushrev(tree[x].ch[0]);
		pushrev(tree[x].ch[1]);
		tree[x].rev = 0;
	}
}
int Get(int x){
	//返回x为左儿子还是右儿子
	return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
	int y = tree[x].fa,z=tree[y].fa,chk=Get(x);
	tree[y].ch[chk] = tree[x].ch[chk^1];
	if(tree[x].ch[chk^1]) tree[tree[x].ch[chk^1]].fa = y;
	tree[x].ch[chk^1] = y;
	tree[y].fa = x;
	if(z)tree[z].ch[y==tree[z].ch[1]] = x;
	tree[x].fa = z;
	pushup(y);
	pushup(x);
}
void splay(int x,int k){
	while(tree[x].fa!=k){
		int y = tree[x].fa,z=tree[y].fa;
		if(z!=k){
			if(Get(x)==Get(y))rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if(k==0)root = x;
}
int kth(int x){
	int cur = root;
	while(cur){
		pushdown(cur);
		if(x<=tree[tree[cur].ch[0]].size){
			cur = tree[cur].ch[0];
		}
		else{
			x-=tree[tree[cur].ch[0]].size;
			if(x<=1){
				splay(cur,0);
				return cur;
			}
			else{
				x--;
				cur = tree[cur].ch[1];
			}
		}
	}
	return -1;
}
void run(int x,int y){
	x++;y++;
	int L = kth(x-1);
	int R = kth(y+1);
	splay(L,0);
	splay(R,L);
	pushrev(tree[R].ch[0]);
}
void insert(int x){
	int cur = root;
	int fa = 0;
	while(cur){
		fa = cur;
		cur = tree[cur].ch[x>tree[cur].val];
	}
	cur = ++tot;
	tree[cur].val = x;
	tree[cur].fa = fa;
	tree[fa].ch[x>tree[fa].val] = cur;
	pushup(cur);
	pushup(fa);
	splay(cur,0);
}
void print(int x){
	pushdown(x);
	if(tree[x].ch[0])print(tree[x].ch[0]);
	if(tree[x].val>=1 && tree[x].val<=n)cout<<tree[x].val<<" ";
	if(tree[x].ch[1])print(tree[x].ch[1]);
}
int main(){
	cin>>n>>m;
	for(int i=0;i<=n+1;i++){
		insert(i);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		run(x,y);
	}
	print(root);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
#define int long long
int n,m,r,p;
int son[N],siz[N],dep[N],fa[N];
int top[N],a[N],wt[N],id[N];
int tree[N<<2],tag[N<<2],cnt;
vector<int>e[N];
void dfs1(int x,int f,int deep){
	fa[x] = f;
	siz[x] = 1;
	dep[x] = deep;
	int maxx = 0;
	for(auto v:e[x]){
		if(v==f)continue;
		dfs1(v,x,deep+1);
		siz[x]+=siz[v];
		if(siz[v]>maxx){
			son[x] = v;
			maxx = siz[v];
		}
	}
}
void dfs2(int x,int topfa){
	top[x] = topfa;
	id[x] = ++cnt;
	wt[cnt] = a[x];
	if(!son[x])return;
	dfs2(son[x],topfa);
	for(auto v:e[x]){
		if(v==fa[x] || v==son[x])continue;
		dfs2(v,v);
	}
}
void pushup(int rt){
	tree[rt] = tree[rt<<1] + tree[rt<<1|1];tree[rt]%=p;
}
void pushdown(int l,int r,int rt){
	if(tag[rt]){
		tag[rt<<1]+=tag[rt];tag[rt<<1]%=p;
		tag[rt<<1|1]+=tag[rt];tag[rt<<1|1]%=p;
		int mid = (l+r)>>1;
		tree[rt<<1]+=tag[rt]*(mid-l+1);tree[rt<<1]%=p;
		tree[rt<<1|1]+=tag[rt]*(r-mid);tree[rt<<1|1]%=p;
		tag[rt] = 0;
	}
}
void build(int l,int r,int rt){
	if(l==r){
		tree[rt] = wt[l];
		return;
	}
	int mid = (l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c){
	c%=p;
	if(L<=l && r<=R){
		tag[rt]+=c;tag[rt]%=p;
		tree[rt]+=c*(r-l+1)%p;tree[rt]%=p;
		return;
	}
	int mid = (l+r)>>1;
	pushdown(l,r,rt);
	if(L<=mid)update(l,mid,rt<<1,L,R,c);
	if(R>mid)update(mid+1,r,rt<<1|1,L,R,c);
	pushup(rt);
}
int query(int l,int r,int rt,int L,int R){
	if(L<=l && r<=R){
		return tree[rt];
	}
	pushdown(l,r,rt);
	int mid = (l+r)>>1;
	int res = 0;
	if(L<=mid)res+=query(l,mid,rt<<1 ,L,R),res%=p;
	if(R>mid)res+=query(mid+1,r,rt<<1|1,L,R),res%=p;
	return res%p;
}
void op1(int x,int y,int z){
	z%=p;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]])swap(x,y);
		update(1,n,1,id[top[y]],id[y],z);
		y = fa[top[y]];
	}
	if(dep[x]>dep[y])swap(x,y);
	update(1,n,1,id[x],id[y],z);
}
int op2(int x,int y){
	int res = 0;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]])swap(x,y);
		res+=query(1,n,1,id[top[y]],id[y]);res%=p;
		y = fa[top[y]];
	}
	if(dep[x]>dep[y])swap(x,y);
	res+=query(1,n,1,id[x],id[y]);
	res%=p;
	return res;
}
void op3(int x,int z){
	z%=p;
	update(1,n,1,id[x],id[x]+siz[x]-1,z);
}
int op4(int x){
	return query(1,n,1,id[x],id[x]+siz[x]-1)%p;
}
signed main(){
	cin>>n>>m>>r>>p;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(r,0,1);
	dfs2(r,r);
	build(1,n,1);
	while(m--){
		int op,x,y,z;
		cin>>op>>x;
		if(op==1){
			cin>>y>>z;
			op1(x,y,z);
		}
		else if(op==2){
			cin>>y;
			cout<<op2(x,y)<<endl;
		}
		else if(op==3){
			cin>>z;
			op3(x,z);
		}
		else {
			cout<<op4(x)<<endl;
		}
	}
	return 0;
}