#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, m, dep[N], son[N], fa[N], siz[N], P;
int top[N], id[N], w[N], wt[N], tot, rt;
int tree[N << 2], tag[N << 2];
vector<int>e[N];

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	fa[x] = f;
	siz[x] = 1;
	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) {
			maxx = siz[v];
			son[x] = v;
		}
	}
}

void dfs2(int x, int topfa) {
	top[x] = topfa;
	id[x] = ++tot;
	wt[tot] = w[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) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		tree[rt] += c * (r - l + 1);
		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 sum = 0;
	if (L <= mid)
		sum += query(l, mid, rt << 1, L, R), sum %= P;
	if (R > mid)
		sum += query(mid + 1, r, rt << 1 | 1, L, R), sum %= P;
	return sum;
}

void pos1(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[x]], id[x], z);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	update(1, n, 1, id[x], id[y], z);
}

int pos2(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[y], id[x]);
	res %= P;
	return res;
}

void pos3(int x, int z) {
	z %= P;
	update(1, n, 1, id[x], id[x] + siz[x] - 1, z);
}

int pos4(int x) {
	return query(1, n, 1, id[x], id[x] + siz[x] - 1) % P;
}

signed main() {
	cin >> n >> m >> rt >> P;
	for (int i = 1; i <= n; i++) {
		cin >> w[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(rt, 0, 1);
	dfs2(rt, rt);
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int pos, x, y, z;
		cin >> pos;
		if (pos == 1) {
			cin >> x >> y >> z;
			pos1(x, y, z);
		} else if (pos == 2) {
			cin >> x >> y;
			cout << pos2(x, y) << endl;
		} else if (pos == 3) {
			cin >> x >> z;
			pos3(x, z);
		} else if (pos == 4) {
			cin >> x;
			cout << pos4(x) << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, m, dep[N], son[N], fa[N], siz[N], P;
int top[N], id[N], w[N], wt[N], tot, rt;
int tree[N << 2], tag[N << 2];
vector<int>e[N];

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	fa[x] = f;
	siz[x] = 1;
	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) {
			maxx = siz[v];
			son[x] = v;
		}
	}
}

void dfs2(int x, int topfa) {
	top[x] = topfa;
	id[x] = ++tot;
	wt[tot] = w[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];
}

void pushdown(int l, int r, int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		int mid = (l + r) >> 1;
		tree[rt << 1] += tag[rt] * (mid - l + 1);
		tree[rt << 1 | 1] += tag[rt] * (r - mid);
		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) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		tree[rt] += c * (r - l + 1);
		return;
	}
	pushdown(l, r, rt);
	int mid = (l + r) >> 1;
	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 p) {
	if (l == r) {
		return tree[rt];
	}
	pushdown(l, r, rt);
	int mid = (l + r) >> 1;
	if (p <= mid)
		return query(l, mid, rt << 1, p);
	else
		return query(mid + 1, r, rt << 1 | 1, p);
}

void pos1(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]])
			swap(x, y);
		update(1, n, 1, id[top[y]], id[y], 1);
		y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	if (x != y) {
		update(1, n, 1, id[x] + 1, id[y], 1);
	}
}

int pos2(int x, int y) {
	if (dep[y] > dep[x])
		return query(1, n, 1, id[y]);
	else
		return query(1, n, 1, id[x]);
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1, 0, 1);
	dfs2(1, 1);
	build(1, n, 1);
	while (m--) {
		char pos;
		int x, y;
		cin >> pos >> x >> y;
		if (pos == 'P') {
			pos1(x, y);
		} else
			cout << pos2(x, y) << endl;
	}
	return 0;
}