m@main=getLine>>=putStrLn.f.words>>m
f[x,y,t]|a:b<-t,z<-f[x,y,b],z/=b=a:z|x<t,x++"~">t=y++drop(length x)t|0<1=t