#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, m, root, Mod;
int dep[N], fa[N], son[N], siz[N]; //dep深度，fa父亲，son重儿子，siz子树大小
int id[N], w[N], top[N]; //id编号，w权值，top重链的链顶
int a[N], cnt;
int tree[N << 2], tag[N << 2];
vector<int>e[N];

void dfs1(int x, int f, int deep) {
	siz[x] = 1;
	fa[x] = f;
	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;
	w[id[x]] = 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] %= Mod;
}

void pushdown(int l, int r, int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1] %= Mod;
		tag[rt << 1 | 1] += tag[rt];
		tag[rt << 1 | 1] %= Mod;
		int mid = (l + r) >> 1;
		tree[rt << 1] += tag[rt] * (mid - l + 1);
		tree[rt << 1] %= Mod;
		tree[rt << 1 | 1] += tag[rt] * (r - mid);
		tree[rt << 1 | 1] %= Mod;
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = w[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 %= Mod;
	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 L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	pushdown(l, r, rt);
	int res = 0, mid = (l + r) >> 1;
	if (L <= mid)
		res += query(l, mid, rt << 1, L, R), res %= Mod;
	if (R > mid)
		res += query(mid + 1, r, rt << 1 | 1, L, R), res %= Mod;
	return res;
}

void pos1(int x, int y, int z) {
	z %= Mod;
	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 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 %= Mod;
		y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	res += query(1, n, 1, id[x], id[y]);
	res %= Mod;
	return res;
}

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

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

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

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, a[N], dep[N], fa[N], siz[N], son[N];
int tree[N << 2], tag[N << 2], tag1[N << 2], tag2[N << 2], top[N], id[N], w[N], cnt;
int U[N], V[N], W[N];

/*
tag[rt]代表rt节点是否有修改操作
tag1[rt]代表rt节点增加了多少
tag2[rt]代表rt节点被修改成什么
*/
struct node {
	int v, w;
};
vector<node>e[N];

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	fa[x] = f;
	siz[x] = 1;
	int maxx = 0;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int w = e[x][i].w;
		if (v == f)
			continue;
		a[v] = w;
		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) {
	id[x] = ++cnt;
	top[x] = topfa;
	w[id[x]] = a[x];
	if (!son[x])
		return;
	dfs2(son[x], topfa);
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		if (v == fa[x] || v == son[x])
			continue;
		dfs2(v, v);
	}
}

void pushup(int rt) {
	tree[rt] = max(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];
		tag1[rt << 1] = tag1[rt];
		tag1[rt << 1 | 1] = tag1[rt];
		tag2[rt << 1] = tag2[rt];
		tag2[rt << 1 | 1] = tag2[rt];
		int mid = (l + r) >> 1;
		tree[rt << 1] = (tag1[rt] + tag2[rt]);
		tree[rt << 1 | 1] = (tag1[rt] + tag2[rt]);
		tag[rt] = 0;
		tag1[rt] = 0;
		tag2[rt] = 0;
	}
	else if(tag1[rt]){
		tag1[rt<<1]+=tag1[rt];
		tag1[rt<<1|1]+=tag1[rt];
		tree[rt<<1]+=tag1[rt];
		tree[rt<<1|1]+=tag1[rt];
		tag1[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = w[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) {
		tag1[rt] += c;
		tree[rt] += c;
		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);
}

void change(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tag[rt] = 1;
		tag1[rt] = 0;
		tag2[rt] = c;
		tree[rt] = c;
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(l, r, rt);
	if (L <= mid)
		change(l, mid, rt << 1, L, R, c);
	if (R > mid)
		change(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];
	}
	int mid = (l + r) >> 1;
	pushdown(l, r, rt);
	int res = -1e18;
	if (L <= mid)
		res = max(res, query(l, mid, rt << 1, L, R));
	if (R > mid)
		res = max(res, query(mid + 1, r, rt << 1 | 1, L, R));
	return res;
}

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

void pos1(int x, int y) {
	int u = U[x], v = V[x];
	pos2(u, v, y);
}

void pos3(int x, int y, int z) {
	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);
	if (x != y)
		update(1, n, 1, id[x] + 1, id[y], z);
}

int pos4(int x, int y) {
	int res = -1e18;
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]])
			swap(x, y);
		res = max(res, query(1, n, 1, id[top[y]], id[y]));
		y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	if (x != y)
		res = max(res, query(1, n, 1, id[x] + 1, id[y]));
	return res;
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		U[i] = x;
		V[i] = y;
		W[i] = z;
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	dfs1(1, 0, 1);
	dfs2(1, 1);
	build(1, n, 1);
	string s;
	while (cin >> s) {
		int x, y, z;
		if (s == "Stop")
			break;
		else if (s == "Max") {
			cin >> x >> y;
			cout << pos4(x, y) << endl;
		} else if (s == "Change") {
			cin >> x >> y;
			pos1(x, y);
		} else if (s == "Cover") {
			cin >> x >> y >> z;
			pos2(x, y, z);
		} else if (s == "Add") {
			cin >> x >> y >> z;
			pos3(x, y, z);
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, dep[N], fa[N], son[N], siz[N];
int top[N], id[N], w[N], cnt, lst[N];
int tree[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] = ++cnt;
	lst[cnt] = 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] = min(tree[rt << 1], tree[rt << 1 | 1]);
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = 1e9;
		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 p) {
	if (l == r) {
		if (tree[rt] != 1e9) {
			tree[rt] = 1e9;
		} else
			tree[rt] = l;
		return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid)
		update(l, mid, rt << 1, p);
	else
		update(mid + 1, r, rt << 1 | 1, p);
	pushup(rt);
}

int query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	int res = 1e9;
	int mid = (l + r) >> 1;
	if (L <= mid)
		res = min(res, query(l, mid, rt << 1, L, R));
	if (R > mid)
		res = min(res, query(mid + 1, r, rt << 1 | 1, L, R));
	return res;
}

void pos1(int x) {
	update(1, n, 1, id[x]);
}

int pos2(int x) {
	int y = 1, res = 1e9;
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]])
			swap(x, y);
		res = min(res, query(1, n, 1, id[top[y]], id[y]));
		y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	res = min(res, query(1, n, 1, id[x], id[y]));
	return res;
}

int 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--) {
		int op, x;
		cin >> op >> x;
		if (op == 0)
			pos1(x);
		else {
			int res = pos2(x);
			if (res == 1e9)
				cout << -1 << endl;
			else
				cout << lst[res] << endl;
		}
	}
	return 0;
}

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

void dfs1(int x, int f, int deep) {
	fa[x] = f;
	dep[x] = deep;
	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) {
	id[x] = ++cnt;
	top[x] = topfa;
	w[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] = min(tree[rt << 1], tree[rt << 1 | 1]);
}

void pushdown(int rt) {
	if (tag[rt]) {
		tag[rt << 1] = tag[rt];
		tag[rt << 1 | 1] = tag[rt];
		tree[rt << 1] = tag[rt];
		tree[rt << 1 | 1] = tag[rt];
		tag[rt] = 0;
	}
}

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

void pos1(int x) {
	root = x;
}

void pos2(int x, int y, int z) {
	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 findroot(int x) {
	int y = root;
	while (id[top[y]] > id[x] && id[top[y]] <= id[x] + siz[x] - 1) {
		y = top[y];
		if (fa[y] == x)
			return y;
		else
			y = fa[top[y]];
	}
	while (fa[y] != x) {
		y = fa[y];
	}
	return y;

}

int pos3(int x) {
	//询问x的子树
	//cout << x << endl;
	if (x == root) {
		return tree[1];
	} else if (id[root] > id[x] && id[root] <= id[x] + siz[x] - 1) {
		//找x的亲儿子y，让root在y的子树里
		int y = findroot(x);
		int res = 1e9;
		if (id[y] != 1)
			res = query(1, n, 1, 1, id[y] - 1);
		if (id[y] + siz[y] <= n)
			res = min(res, query(1, n, 1, id[y] + siz[y], n));
		return res;
	} else {
		return query(1, n, 1, id[x], id[x] + siz[x] - 1);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	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);
	}
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	cin >> root;
	dfs1(1, 0, 1);
	dfs2(1, 1);
	build(1, n, 1);
	while (m--) {
		int op, x, y, z;
		cin >> op;
		if (op == 1) {
			cin >> x;
			pos1(x);
		} else if (op == 2) {
			cin >> x >> y >> z;
			pos2(x, y, z);
		} else {
			cin >> x;
			cout << pos3(x) <<'\n';
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, Inf = 1e9;
int n, m, dep[N], fa[N], siz[N], son[N];
int top[N], id[N], cnt, w[N], a[N];

struct node {
	int Max, Min, val, L_R, R_L;
	friend node operator + (node a, node b) {
		node c;
		if (a.Max == -Inf && a.Min == Inf && a.val == 0 && a.L_R == 0 && a.R_L == 0)
			return b;
		if (b.Max == -Inf && b.Min == Inf && b.val == 0 && b.L_R == 0 && b.R_L == 0)
			return a;
		c.Max = max(a.Max, b.Max);
		c.Min = min(a.Min, b.Min);
		c.L_R = max(max(a.L_R, b.L_R), b.Max - a.Min);
		c.R_L = max(max(a.R_L, b.R_L), a.Max - b.Min);
		c.val = max(max(a.val, b.val), max(c.L_R, c.R_L));
		return c;
	}
} tree[N << 2];
int tag[N << 2];
vector<int>e[N];

void dfs1(int x, int f, int deep) {
	dep[x] = deep + 1;
	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] = ++cnt;
	w[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];
}

void pushdown(int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		tree[rt << 1].Max += tag[rt];
		tree[rt << 1].Min += tag[rt];
		tree[rt << 1 | 1].Max += tag[rt];
		tree[rt << 1 | 1].Min += tag[rt];
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = {w[l], w[l], 0, 0, 0};
		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].Max += c;
		tree[rt].Min += c;
		return;
	}
	pushdown(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);
}

node query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	node res = {-Inf, Inf, 0, 0, 0};
	pushdown(rt);
	int mid = (l + r) >> 1;
	if (L <= mid)
		res = res + query(l, mid, rt << 1, L, R);
	if (R > mid)
		res = res + query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

void pos1(int x, int y, int z) {
	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);
}

node pos2(int x, int y) {
	node Lc = {-Inf, Inf, 0, 0, 0}, Rc = {-Inf, Inf, 0, 0, 0};
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]]) {
			node tmp = query(1, n, 1, id[top[x]], id[x]);
			swap(tmp.L_R, tmp.R_L);
			Lc = Lc + tmp;
			x = fa[top[x]];
		} else {
			node tmp = query(1, n, 1, id[top[y]], id[y]);
			Rc = tmp + Rc;
			y = fa[top[y]];
		}
	}
	if (dep[x] > dep[y]) {
		node tmp = query(1, n, 1, id[y], id[x]);
		swap(tmp.L_R, tmp.R_L);
		Rc = tmp + Rc;
		return Lc + Rc;
	} else {
		node tmp = query(1, n, 1, id[x], id[y]);
		Rc = tmp + Rc;
		return Lc + Rc;
	}
}

int main() {
	cin >> n;
	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(1, 0, 1);
	dfs2(1, 1);
	build(1, n, 1);
	cin >> m;
	while (m--) {
		int x, y, z;
		cin >> x >> y >> z;

		cout << pos2(x, y).L_R << endl;
		pos1(x, y, z);
	}
	return 0;
}