Description:

Solution:

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<map>

#include<cstring>

using namespace std;

#define MAXC 11

#define MAXN 10010

int n,m,c,k;

map<pair<int,int>,int> col;

int cnt[MAXC][MAXN];

struct node

{

	int c[2],fa,v,maxv;

	bool rev;

	int& operator [](int x){return c[x];}

	node(){c[0] = c[1] = fa = v = maxv = 0;rev = false;}

}t[MAXC][MAXN];

void maintain(int p,int k){

	t[p][k].maxv = t[p][k].v;

	if(t[p][k][0] != 0)t[p][k].maxv = max(t[p][k].maxv,t[p][t[p][k][0]].maxv);

	if(t[p][k][1] != 0)t[p][k].maxv = max(t[p][k].maxv,t[p][t[p][k][1]].maxv);

	return;

}

bool isroot(int p,int k){return (t[p][t[p][k].fa][0] != k && t[p][t[p][k].fa][1] != k);}

int id(int p,int k){return (t[p][t[p][k].fa][0] == k ? 0 : 1);}

void connect(int p,int k,int f,int type){t[p][k].fa = f;t[p][f][type] = k;return;}

void rotate(int p,int x){

	int y = t[p][x].fa,z = t[p][y].fa,fx = id(p,x),fy = id(p,y);

	if(!isroot(p,y))t[p][z][fy] = x;

	t[p][x].fa = z;

	connect(p,t[p][x][fx^1],y,fx);

	connect(p,y,x,fx^1);

	maintain(p,y);maintain(p,x);

	return;

}

stack<int> s;

void pushdown(int p,int k){

	if(!t[p][k].rev)return;

	t[p][t[p][k][0]].rev ^= 1;t[p][t[p][k][1]].rev ^= 1;

	swap(t[p][k][0],t[p][k][1]);t[p][k].rev = false;

	return;

}

void splay(int p,int x){

	s.push(x);

	for(int i = x;!isroot(p,i);i = t[p][i].fa)s.push(t[p][i].fa);

	while(!s.empty()){pushdown(p,s.top());s.pop();}

	while(!isroot(p,x))

	{

		int y = t[p][x].fa;

		if(isroot(p,y)){rotate(p,x);break;}

		if(id(p,x) == id(p,y)){rotate(p,y);rotate(p,x);}

		else{rotate(p,x);rotate(p,x);}

	}

	return;

}

void access(int p,int k){for(int i = 0;k;i = k,k = t[p][k].fa){splay(p,k);t[p][k].c[1] = i;maintain(p,k);}return;}

void makeroot(int p,int k){access(p,k);splay(p,k);t[p][k].rev ^= 1;return;}

void cut(int p,int x,int y){makeroot(p,x);access(p,y);splay(p,y);t[p][x].fa = t[p][y][0] = 0;maintain(p,y);return;}

void link(int p,int x,int y){makeroot(p,x);t[p][x].fa = y;return;}

int find(int p,int k){access(p,k);splay(p,k);while(true){pushdown(p,k);if(t[p][k][0] != 0)k = t[p][k][0];else return k;}}

int main()

{

	scanf("%d%d%d%d",&n,&m,&c,&k);

	int a;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a);

		for(int j = 1;j <= c;++j)t[j][i].v = t[j][i].maxv = a;

	}

	int u,v,w;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&u,&v,&w);++w;

		if(u > v)swap(u,v);

		link(w,u,v);col[make_pair(u,v)] = w;

		++cnt[w][u];++cnt[w][v];

	}

	int opt;

	for(int i = 1;i <= k;++i)

	{

		scanf("%d",&opt);

		if(opt == 0)

		{

			scanf("%d%d",&u,&v);

			for(int p = 1;p <= c;++p){makeroot(p,u);t[p][u].v = v;maintain(p,u);}

			continue;

		}

		if(opt == 1)

		{

			scanf("%d%d%d",&u,&v,&w);++w;

			if(u > v)swap(u,v);

			if(!col.count(make_pair(u,v))){puts("No such edge.");continue;}

			if(col[make_pair(u,v)] == w){puts("Success.");continue;}

			if(cnt[w][u] == 2 || cnt[w][v] == 2){puts("Error 1.");continue;}

			if(find(w,u) == find(w,v)){puts("Error 2.");continue;} 

			int h = col[make_pair(u,v)];

			cut(h,u,v);link(w,u,v);col[make_pair(u,v)] = w;

			--cnt[h][u];--cnt[h][v];

			++cnt[w][u];++cnt[w][v];

			puts("Success.");

		}

		if(opt == 2)

		{

			scanf("%d%d%d",&w,&u,&v);++w;

			if(find(w,u) != find(w,v)){puts("-1");continue;}

			else{makeroot(w,u);access(w,v);splay(w,v);printf("%d\n",t[w][v].maxv);}

		}

	}

	return 0;

}