#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 50010 << 1;
const ll INF = 1e18;
struct LCTNode
{
int ch[2], fa;
ll val, sum, min_w;
bool rev, active;
LCTNode() : fa(0), rev(false), active(true)
{
ch[0] = ch[1] = 0;
val = sum = 0;
min_w = INF;
}
} tr[MAXN];
bool is_root(int x) {
return tr[tr[x].fa].ch[0] != x && tr[tr[x].fa].ch[1] != x;
}
void pushup(int x)
{
tr[x].sum = tr[x].val;
tr[x].min_w = tr[x].val;
if (tr[x].ch[0])
{
tr[x].sum += tr[tr[x].ch[0]].sum;
tr[x].min_w = min(tr[x].min_w, tr[tr[x].ch[0]].min_w);
}
if (tr[x].ch[1])
{
tr[x].sum += tr[tr[x].ch[1]].sum;
tr[x].min_w = min(tr[x].min_w, tr[tr[x].ch[1]].min_w);
}
}
void pushrev(int x)
{
swap(tr[x].ch[0], tr[x].ch[1]);
tr[x].rev ^= 1;
}
void pushdown(int x)
{
if (tr[x].rev)
{
if (tr[x].ch[0]) pushrev(tr[x].ch[0]);
if (tr[x].ch[1]) pushrev(tr[x].ch[1]);
tr[x].rev = false;
}
}
void rotate(int x) {
int y = tr[x].fa, z = tr[y].fa;
int k = (tr[y].ch[1] == x);
if (!is_root(y)) tr[z].ch[tr[z].ch[1] == y] = x;
tr[x].fa = z;
tr[y].ch[k] = tr[x].ch[k ^ 1];
if (tr[x].ch[k ^ 1]) tr[tr[x].ch[k ^ 1]].fa = y;
tr[x].ch[k ^ 1] = y;
tr[y].fa = x;
pushup(y);
pushup(x);
}
void splay(int x)
{
static int stk[MAXN], top = 0;
stk[++top] = x;
for (int i = x; !is_root(i); i = tr[i].fa) stk[++top] = tr[i].fa;
while (top) pushdown(stk[top--]);
while (!is_root(x))
{
int y = tr[x].fa, z = tr[y].fa;
if (!is_root(y)) rotate((tr[y].ch[0] == x) ^ (tr[z].ch[0] == y) ? x : y);
rotate(x);
}
pushup(x);
}
void access(int x)
{
for (int y = 0; x; y = x, x = tr[x].fa)
{
splay(x);
tr[x].ch[1] = y;
pushup(x);
}
}
void make_root(int x)
{
access(x);
splay(x);
pushrev(x);
}
void link(int x, int y)
{
make_root(x);
tr[x].fa = y;
}
void cut(int x, int y)
{
make_root(x);
access(y);
splay(y);
tr[y].ch[0] = tr[x].fa = 0;
pushup(y);
}
bool connected(int x, int y)
{
make_root(x);
access(y);
splay(y);
while (tr[y].ch[0]) y = tr[y].ch[0];
return y == x;
}
pair<ll, ll> query_path(int v, int u)
{
make_root(v);
access(u);
splay(u);
return {tr[u].min_w, tr[u].sum};
}
void update_path(int v, int u, ll d)
{
make_root(v);
access(u);
splay(u);
static int path[MAXN], cnt = 0;
cnt = 0;
auto dfs = [&](auto& self, int x) -> void
{
if (!x) return;
pushdown(x);
tr[x].val += d;
path[++cnt] = x;
self(self, tr[x].ch[0]);
self(self, tr[x].ch[1]);
};
dfs(dfs, u);
for (int i = cnt; i >= 1; --i) pushup(path[i]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T, n, m, k;
cin >> T >> n >> m >> k;
for (int i = 1; i <= n; ++i)
{
cin >> tr[i].val;
tr[i].sum = tr[i].val;
tr[i].min_w = tr[i].val;
}
int edge_id = n + 1;
while (m--)
{
string op;
cin >> op;
if (op == "link")
{
int v, u, w;
cin >> v >> u >> w;
link(v, u);
cout << "ok\n";
} else if (op == "cut")
{
int v, u, w;
cin >> v >> u >> w;
cut(v, u);
cout << "ok\n";
} else if (op == "query1")
{
int v, u;
cin >> v >> u;
if (!connected(v, u))
{
cout << "-1 -1\n";
continue;
}
auto [min_w, sum_w] = query_path(v, u);
cout << min_w << " " << sum_w << "\n";
} else if (op == "add1")
{
int v,u;
ll d;
cin >> v >> u >> d;
if (!connected(v, u))
{
cout << "failed\n";
continue;
}
update_path(v, u, d);
}
}
return 0;
}
