记录
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO{
#define IOSIZE 100000
char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
inline void print(char x) { putchar(x); }
inline void print(char *x) { while (*x) putchar(*x++); }
inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
inline void print(bool b) { putchar(b+48); }
template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
}using namespace fast_IO;
const int N=1e6+10;
mt19937 rnd(time(0));
int n,q,head[N],ed[N],cnt,root[N],tot,p[N],ma;
struct node{
int val,lst,nxt;
}d[N];
inline void add(int x,int val){
++cnt;
d[cnt].val=val;
if(!head[x]){
head[x]=ed[x]=cnt;
return;
}
d[ed[x]].nxt=cnt;
d[cnt].lst=ed[x];
ed[x]=cnt;
}
struct tree{
int lson,rson,siz;
}t[N*50];
inline void update(int &u,int l,int r,int x,int val){
if(!u)u=++tot;
t[u].siz+=val;
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)update(t[u].lson,l,mid,x,val);
else update(t[u].rson,mid+1,r,x,val);
}
inline int query(int u,int l,int r,int x){
if(!t[u].siz)return 0;
if(l==r)return t[u].siz;
int mid=(l+r)>>1;
if(x<=mid)return query(t[u].lson,l,mid,x);
else return query(t[u].rson,mid+1,r,x);
}
inline int merge(int a,int b){
if(!a||!b)return a|b;
t[a].siz+=t[b].siz;
t[a].lson=merge(t[a].lson,t[b].lson);
t[a].rson=merge(t[a].rson,t[b].rson);
return a;
}
inline int kth(int u,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1;
if(t[t[u].lson].siz>=k)return kth(t[u].lson,l,mid,k);
else return kth(t[u].rson,mid+1,r,k-t[t[u].lson].siz);
}
signed main(){
cin>>n>>q;
ma=n+q;
for(int i=1;i<=n;++i){
int len,x;
cin>>len;
for(int j=1;j<=len;++j){
cin>>x;
add(i,x);
update(root[i],1,ma,x,1);
}
}
int opt,x1,x2,x3;
while(q--){
cin>>opt;
if(opt==1){
cin>>x1>>x2;
add(x1,x2);
update(root[x1],1,ma,x2,1);
}
if(opt==2){
cin>>x1;
update(root[x1],1,ma,d[ed[x1]].val,-1);
ed[x1]=d[ed[x1]].lst;
if(!ed[x1])head[x1]=0;
}
if(opt==4){
cin>>x1>>x2>>x3;
if(!head[x1]||!head[x2]){
head[x3]=head[x1]|head[x2];
ed[x3]=ed[x1]|ed[x2];
root[x3]=root[x1]|root[x2];
continue;
}
d[ed[x1]].nxt=head[x2];
d[head[x2]].lst=ed[x1];
head[x3]=head[x1];
ed[x3]=ed[x2];
root[x3]=merge(root[x1],root[x2]);
}
if(opt==3){
int len,siz=0;
cin>>len;
for(int i=1;i<=len;++i)cin>>p[i],siz+=t[root[p[i]]].siz;
int limit=30,ans=-1;
while(limit--){
int pos=rnd()%siz+1,val=0,sum=0;
for(int i=1;i<=len;++i){
if(pos<=t[root[p[i]]].siz){
val=kth(root[p[i]],1,ma,pos);
break;
}
else pos-=t[root[p[i]]].siz;
}
for(int i=1;i<=len;++i)sum+=query(root[p[i]],1,ma,val);
if(sum*2>siz){
ans=val;
break;
}
}
cout<<ans<<"\n";
}
}
cerr<<"Time: "<<clock()/1.0/CLOCKS_PER_SEC*1000.0<<" ms\n";
return 0;
}