Description
量子力学指出，宇宙并非只有一种形态。
根据量子理论，一件事件发生之后可以产生不同的后果，而所有可能的后果都会形成自己的宇宙。
我们可以把一个宇宙看成一个时间轴，虫洞可以看成不同宇宙的不同时间之间的跳跃。虫洞非常的不稳定，存在时间只有一瞬间。
如果存在虫洞事件(U1,t1,U2,t2)那么在宇宙U1的t1时间和宇宙U2的t2时间会被连接，此时就会发生时空跳跃现象。
你可以认为：同一个宇宙同一个时刻最多只存在一个虫洞事件。
为了研究虫洞的性质，科学家向宇宙深处发射了虫洞探测器。
该探测器会检测到自己存在的宇宙中的虫洞事件，并且一旦检测到虫洞事件就一定会进行跳跃。
由于科学家并不确定虫洞事件的具体位置时间，所以暂时用电脑模拟很多平行宇宙以及虫洞事件。
你将被告之探测器被放出时所在的宇宙名称和时间。
你需要处理以下信息：
1. “ADD U1 t1 U2 t2” 表示在模拟中加入一个虫洞事件(U1,t1,U2,t2),其中U1和U2是字符串，t1和t2是32位非负整数
2. “DEL U1 t1 U2 t2” 表示删除之前加入过的一个虫洞事件，保证该事件之前被ADD过。
3. “QUERY” 表示询问探测器经过足够久的时间后会落入哪个宇宙，输出宇宙名称。如果答案不确定，请输出“*”
Input
第一行: U0 t0 表示探测器发射的地点和时间。保证该时刻不存在虫洞事件。
第二行： 正整数 Q 表示操作数
接下来 Q 行: 2种操作，如描述，ADD或ASK。无多余字符。
Output
按照输入顺序，回答每一个ASK操作，直接输出宇宙名称或者“*”，每个回答占一行。
将每个有事件的时刻建一个点表示，每个点有且只有一个后继，构成基环内向树森林，查询就是查环上是否同色，如果是的话输出颜色，可用lct维护
#include<bits/stdc++.h>
int _(){
int x=,f=,c=getchar();
while(c<)c=='-'?f=-:,c=getchar();
while(c>)x=x*+c-,c=getchar();
return x*f;
}
void _(char*s){
scanf("%s",s);
}
char ss[][],s[];
int nx[][],ptr=,st1,st2,idp=,qs[][],qp,ids[];
std::vector<int>e[];
struct node{
node*c[],*f,*ff;
int id,ida;
bool nrt(){return this==f->c[]||this==f->c[];}
void up();
}ns[],*nil=ns;
void node::up(){
ida=(c[]!=nil&&c[]->ida!=id||c[]!=nil&&c[]->ida!=id)?:id;
}
void rot(node*w){
node*f=w->f,*g=f->f;
int d=f->c[]==w;
if(f->nrt())g->c[g->c[]==f]=w;
w->f=g;
(f->c[d]=w->c[d^])->f=f;
(w->c[d^]=f)->f=w;
f->up();
}
void sp(node*w){
while(w->nrt()){
node*f=w->f;
if(f->nrt())rot((w==f->c[])==(f==f->f->c[])?f:w);
rot(w);
}
w->up();
}
node*acs(node*x){
node*y=nil;
for(;x!=nil;sp(x),x->c[]=y,x->up(),y=x,x=x->f);
return y;
}
node*gl(node*w){
while(w->c[]!=nil)w=w->c[];
sp(w);
return w;
}
node*grt(node*w){
node*w0=w;
while(w->f!=nil)w=w->f;
sp(w0);
return w;
}
void lk(node*x,node*y){
node*w=acs(x);
if(grt(y)==w)x->ff=y;
else sp(x),x->f=y;
}
node*ct(node*x){
acs(x),sp(x);
node*y=x->c[];
if(y!=nil){
x->c[]=y->f=nil;
x->up();
y=gl(acs(y));
if(y->ff!=nil&&grt(y->ff)==x){
y->f=y->ff;
y->ff=nil;
}
}else x->ff=nil;
}
int tins(){
int w=;
for(int i=;s[i];++i){
int c=s[i]-'a';
if(!nx[w][c])nx[w][c]=++ptr;
w=nx[w][c];
}
if(!nx[w][]){
nx[w][]=++idp;
strcpy(ss[idp],s);
}
return nx[w][];
}
int gid(int a,int b){
return ids[a]+std::lower_bound(e[a].data(),e[a].data()+e[a].size(),b)-e[a].data();
}
int main(){
_(s);
e[st1=tins()].push_back(st2=_());
qp=_();
for(int i=;i<qp;++i){
_(s);
if(s[]=='Q'){
qs[i][]=;
}else{
qs[i][]=s[]=='A'?:;
_(s);
qs[i][]=tins();
qs[i][]=_();
_(s);
qs[i][]=tins();
qs[i][]=_();
if(qs[i][]==){
e[qs[i][]].push_back(qs[i][]);
e[qs[i][]].push_back(qs[i][]);
}
}
}
ids[]=;
ns[]=(node){nil,nil,nil,nil,,};
for(int i=;i<=idp;++i){
int*l=e[i].data(),*r=l+e[i].size();
std::sort(l,r);
e[i].resize(std::unique(l,r)-l);
int mx=ids[i+]=ids[i]+e[i].size()+;
for(int j=ids[i];j<mx;++j)ns[j]=(node){nil,nil,ns+j+,nil,i,i};
ns[mx-].f=nil;
ns[mx-].ff=ns+mx-;
}
st2=gid(st1,st2);
ss[][]='*';
for(int i=;i<qp;++i){
if(qs[i][]==){
node*w=gl(acs(ns+st2));
puts(ss[acs(w->ff)->ida]);
}else{
int w1=gid(qs[i][],qs[i][]);
int w2=gid(qs[i][],qs[i][]);
ct(ns+w1),ct(ns+w2);
if(qs[i][]==){
lk(ns+w1,ns+w2+);
lk(ns+w2,ns+w1+);
}else{
lk(ns+w1,ns+w1+);
lk(ns+w2,ns+w2+);
}
}
}
return ;
}