#include<iostream>
#include<stack>

using namespace std;

class regnode;
class nfanode;
class ilinknode;
class nunode;
class winlex;
class dlink;
class dfanode;
class dilink;

class regnode
{
private:
	char rval;
	int lnum;
	nfanode *pnfan;
	ilinknode *pilnode;
	regnode *rnext;
	regnode *rpre;
	bool ischar;
	bool insed;
	friend winlex;
	friend nfanode;
	friend dfanode;
public:
	regnode();
};

regnode::regnode()
{
	pnfan=NULL;
	pilnode=NULL;
	rnext=NULL;
	rpre=NULL;
	insed=false;
}

class ilinknode
{
private:
	regnode *ircp;
	nfanode *nnext;
	ilinknode *ilnnext;
	friend winlex;
	friend nfanode;
	friend dfanode;
public:
	ilinknode();
};

ilinknode::ilinknode()
{
	ircp=NULL;
	nnext=NULL;
	ilnnext=NULL;
}

class nunode
{
private:
	nfanode * nunfa;
	nunode * nunext;
	friend winlex;
	friend nfanode;
	friend dfanode;
public:
	nunode();
};

nunode::nunode()
{
	nunfa=NULL;
	nunext=NULL;	
}

class linklist
{
protected:
	linklist * next;
public:
	linklist();
};

linklist::linklist()
{
	next=NULL;
}

class dlink:private linklist
{
private:
	nfanode * pdton;
	friend nfanode;
	friend dfanode;
	friend winlex;
public:
	dlink();
	void dsort(dlink *dshead);
};

dlink::dlink()
{
	pdton=NULL;
}

class nfanode
{
private:
	int nnum;
    ilinknode *ilhead;
	nunode * nuhead;
	bool isstart;
	bool isend;
	nfanode * iins(regnode *ilrp,nfanode *np,int &nfai);
	friend winlex;
	friend dlink;
	friend dfanode;
public:
	nfanode(int & nfai);
};

nfanode::nfanode(int & nfai)
{
    isstart=false;
	isend=false;
	nnum=nfai++;
	nuhead=new nunode();
    ilhead=new ilinknode;
}

nfanode * nfanode::iins(regnode *rp,nfanode *np,int &nfai)
{
	ilinknode *ip;
	ip=new ilinknode;
	ip->ircp=rp;
	rp->pilnode=ip;
	rp->pnfan=np;
	ip->nnext=new nfanode(nfai);
	np=ip->nnext;
    ip->ilnnext=ilhead->ilnnext;
	ilhead->ilnnext=ip;
	return(np);
}

void dlink::dsort(dlink *dshead)
{
	dlink *dp1,*dp2,*dp3;
	dp1=(dlink *)dshead->next;
	if(dp1==NULL)
		return;
	else
	{
        while(dp1->next!=NULL)
        {
            if(dp1->pdton->nnum<=((dlink *)dp1->next)->pdton->nnum)
				dp1=(dlink *)dp1->next;
			else
			{
                dp2=(dlink *)dp1->next;
                dp1->next=dp2->next;
                dp3=dshead;
                while(((dlink *)(dp3->next))->pdton->nnum<dp2->pdton->nnum)
                    dp3=(dlink *)dp3->next;
                dp2->next=dp3->next;
                dp3->next=dp2;
			}
		}
	}
}

class sdlink:protected linklist
{
private:
	friend winlex;
protected:
	char cval;
};

class dilink:protected sdlink
{
private:
	friend dfanode;
	friend winlex;
protected:
	dfanode *pd;
public:
	dilink();
};

class dfanode
{
private:
	dlink * selflinkhead;
	dilink * ilhead;
	int nval;
	bool isend;
    void selflins(nfanode *nfap);
	friend winlex;
public:
	dfanode();
	void dfailins(char cc);
	void dfaclollink();
	void dfasetend(int i);
	void selfclosure();
	void cloins(nunode *nup);
};

dfanode::dfanode()
{
    selflinkhead=new dlink();
	ilhead=new dilink();
	isend=false;
}

void dfanode::cloins(nunode *nup)
{
	dlink *slp,*tsp;
	tsp=selflinkhead;
	slp=(dlink *)selflinkhead->next;
	while(slp!=NULL)
	{
		if(slp->pdton==nup->nunfa)
			return;
		tsp=slp;
		slp=(dlink *)slp->next;
	}
	tsp->next=new dlink();
	slp=(dlink *)tsp->next;
	slp->pdton=nup->nunfa;
}

void dfanode::dfasetend(int i)
{
    dlink *slp;
	slp=selflinkhead;
	while(slp->next!=NULL)
		slp=(dlink *)slp->next;
	if(slp->pdton->nnum==i)
        isend=true;
}

void dfanode::selflins(nfanode *nfap)
{
    dlink *dlp;
	dlp=selflinkhead;
	while(dlp->next!=NULL)
	{
		if(((dlink *)(dlp->next))->pdton==nfap)
			return;
		dlp=(dlink *)dlp->next;
	}
	dlp->next=new dlink();
	dlp=(dlink *)dlp->next;
	dlp->pdton=nfap;
}

void dfanode::dfaclollink()
{
	dilink *dip;
    dip=(dilink *)ilhead->next;
	dip->pd=new dfanode();
    dlink *dp;
	ilinknode *nilp;
	dp=(dlink *)selflinkhead->next;
	while(dp!=NULL)
	{
        nilp=dp->pdton->ilhead->ilnnext;
		while(nilp!=NULL)
		{
            if(nilp->ircp->rval==dip->cval)
				dip->pd->selflins(nilp->nnext);
			nilp=nilp->ilnnext;
		}
		dp=(dlink *)dp->next;
	}
	dip->pd->selfclosure();
}

void dfanode::selfclosure()
{
	nunode *nup;
	dlink *sp;
	sp=(dlink *)selflinkhead->next;
	while(sp!=NULL)
	{
        nup=sp->pdton->nuhead->nunext;
		while(nup!=NULL)
		{
			cloins(nup);
			nup=nup->nunext;
		}
		sp=(dlink *)sp->next;
	}
	selflinkhead->dsort(selflinkhead);
}

void dfanode::dfailins(char cc)
{
	dilink *p;
	p=new dilink();
	p->cval=cc;
	p->next=ilhead->next;
	ilhead->next=p;
}

dilink::dilink()
{
	pd=NULL;
}

class dnlink:private dilink
{
private:
	int nval;
	friend winlex;
public:
	dnlink(int &dfai);
};

dnlink::dnlink(int &dfai)
{
	nval=dfai++;
}