玄关WA on #10#13#16#19#20

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+5;
const int V=1e6+5;

int read(){
	int s=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=s*10+c-'0';
		c=getchar();
	}
	return s*f;
} 

int n,q;
int rt[N<<1],tl[N<<1],mx[N<<5],ls[N<<5],rs[N<<5],tot;
ll val[N<<5],sz[N<<1]; 

void push_up(int p){
	int p1=ls[p],p2=rs[p];
	if(!p1||!p2){
		int son=p1^p2;
		mx[p]=mx[son];
		val[p]=val[son];
		return;
	} 
	if(val[p1]>=val[p2]){
		val[p]=val[p1];
		mx[p]=mx[p1];
	}else{
		val[p]=val[p2];
		mx[p]=mx[p2];
	}
}

void update(int &p,int pl,int pr,int x,int k){
	if(!p)p=++tot; 
	if(pl==pr){
		mx[p]=x;
		val[p]+=k;
		return;
	}
	int mid=pl+pr>>1;
	if(x<=mid)update(ls[p],pl,mid,x,k);
	else update(rs[p],mid+1,pr,x,k);
	push_up(p);
}

void merge(int &p,int q,int pl,int pr){
	if(!p){
		p=q;
		return;
	}
	if(!q)return;
	if(pl==pr){
		val[p] += val[q];
		return;
	}
	int mid=pl+pr>>1;
	merge(ls[p],ls[q],pl,mid);
	merge(rs[p],rs[q],mid+1,pr);
	push_up(p);
}

ll query(int p,int pl,int pr,int x){
	if(!p)return 0;
	if(pl==pr)return val[p];
	int mid=pl+pr>>1;
	if(x<=mid)return query(ls[p],pl,mid,x);
	return query(rs[p],mid+1,pr,x);
}

int qx[N],que[N];
ll quev[N];

int solve(int m){
	int cnt=0;
	ll tsz=0;
	for(int i=1;i<=m;i++){
		int idx=qx[i];
		tsz += sz[idx];
		if(2*val[rt[idx]]>sz[idx]){
			que[++cnt]=mx[rt[idx]];
			quev[cnt]=2*val[rt[idx]]-sz[idx]; 
		}
	}
	int mmx=-1;
	ll mmxv=0;
	for(int i=1;i<=cnt;i++){
		if(mmx==que[i]){
			mmxv+=quev[i];
		}else{
			if(mmxv<quev[i]){
				mmx=que[i];
				mmxv=quev[i]-mmxv;
			}else
				mmxv-=quev[i];
		}
	}
	if(mmx==-1)return -1;
	ll tmp=0;
	for(int i=1;i<=m;i++)
		tmp+=query(rt[qx[i]],1,V,mmx);
	if(tmp*2>tsz)return mmx;
	return -1;
}

int lst[N<<2],to[N<<2],totl;  

signed main(){
	n=read(),q=read();
	tot=0,totl=0;
	for(int i=1;i<=n;i++){
		int l=read();
		sz[i]=l;  
		for(int j=1;j<=l;j++){
			int x=read();  
			lst[++totl]=x;
			to[totl]=tl[i];
			tl[i]=totl;
			update(rt[i],1,V,x,1);
		}
	}
	
	while(q--){
		int op=read();
		if(op==1){ 
			int x=read(),y=read();
			lst[++totl]=y;
			to[totl]=tl[x];
			tl[x]=totl;
			update(rt[x],1,V,y,1);
			sz[x]++;
		}else if(op==2){  
			int x=read();
			int ttl=tl[x]; 
			int y=lst[ttl]; 
			update(rt[x],1,V,y,-1);
			tl[x]=to[ttl];
			sz[x]--;
			if(sz[x]==0)rt[x]=0;
		}else if(op==3){
			int m=read();
			for(int j=1;j<=m;j++)qx[j]=read();
			printf("%d\n",solve(m));
		}else if(op==4){  
			int a=read(),b=read(),c=read();
			rt[c]=0;  
			merge(rt[c],rt[a],1,V);
			merge(rt[c],rt[b],1,V);
			sz[c]=sz[a]+sz[b];
			if(tl[a]){
				tl[c]=tl[b]?tl[b]:tl[a];
				if(tl[b])to[tl[b]]=tl[a];
			}else{
				tl[c]=tl[b];				
			}
			sz[a]=sz[b]=0;
			rt[a]=rt[b]=tl[a]=tl[b]=0;
		}
	}
	return 0;
}