#include<bits/stdc++.h>
using namespace std;
int tr[500005][2];
int rt[200005],pri[500005],val[500005],rev[500005];
int n,q;
int tot;
int newnode(int v){
	tot++;
	tr[tot][0]=tr[tot][1]=0;
	pri[tot]=rand();
	val[tot]=v;
	rev[tot]=0;
	return tot;
}
void pushdown(int x){
	if(!rev[x])return;
	if(tr[x][0]){
		rev[tr[x][0]]^=1;
		swap(tr[tr[x][0]][0],tr[tr[x][0]][1]);
	}
	if(tr[x][1]){
		rev[tr[x][1]]^=1;
		swap(tr[tr[x][1]][0],tr[tr[x][1]][1]);
	}
	rev[x]=0;
}
int merge(int x,int y){
	if(x==0 || y==0)return x+y;
	if(pri[x]<pri[y]){
		pushdown(x);
		tr[x][1]=merge(tr[x][1],y);
		return x;
	}
	else{
		pushdown(y);
		tr[y][0]=merge(x,tr[y][0]);
		return y;
	}
}
void output(int x){
	if(!x)return;
	pushdown(x);
	output(tr[x][0]);
	printf("%d ",val[x]);
	output(tr[x][1]);
}
int main(){
	srand(0114507537);
	while(~scanf("%d%d",&n,&q)){
		for(int i=1;i<=n;i++)rt[i]=0;
		tot=0;
		while(q--){
			int op,u,v,w;
			scanf("%d",&op);
			if(op==1){
				scanf("%d%d%d",&u,&w,&v);
				if(w==0)rt[u]=merge(newnode(v),rt[u]);
				else rt[u]=merge(rt[u],newnode(v));
			}
			if(op==2){
				scanf("%d%d",&u,&w);
				if(rt[u]==0){
					printf("-1\n");
					continue;
				}
				int tmp=rt[u],lst=0;
				pushdown(tmp);
				while(tr[tmp][w]){
					lst=tmp;
					tmp=tr[tmp][w];
					pushdown(tmp);
				}
				if(lst)tr[lst][w]=merge(tr[tmp][0],tr[tmp][1]);
				else rt[u]=merge(tr[tmp][0],tr[tmp][1]);
				printf("%d\n",val[tmp]);
			}
			if(op==3){
				scanf("%d%d%d",&u,&v,&w);
				rev[rt[v]]^=w;
				if(w)swap(tr[rt[v]][0],tr[rt[v]][1]);
				rt[u]=merge(rt[u],rt[v]);
				rt[v]=0;
			}
//			for(int i=1;i<=n;i++){
//				printf("%d:\n",i);
//				output(rt[i]);putchar(10);
//			}
		}
	}
}