struct Trie{	int ch[MAXN][26];	int cnt;	Trie()	{		cnt=1;		memset(ch[0],0,sizeof(ch[0]));	}		int idx(char c)	{		return c-‘a‘;	}		void insert(char *s,int v)	{		int u=0,len=strlen(s);		for (int i=0;i<len;i++)		{			int c=idx(s[i]);			if (!ch[u][c])			{				memset(ch[cnt],0,sizeof(ch[cnt]));				ch[u][c]=cnt++;			}			u=ch[u][c];		}		val[u]=v;	}} tree;

struct ACauto{	int ch[MAXN][26];	int cnt;	int f[MAXN],last[MAXN],val[MAXN];		Trie()	{		cnt=1;		memset(ch[0],0,sizeof(ch[0]));	}		int idx(char c)	{		return c-‘a‘;	}		void insert(char *s,int v)	{		int u=0,len=strlen(s);		for (int i=0;i<len;i++)		{			int c=idx(s[i]);			if (!ch[u][c])			{				memset(ch[cnt],0,sizeof(ch[cnt]));				ch[u][c]=cnt++;			}			u=ch[u][c];		}		val[u]=v;	}		void print(int j)	{		if (j)		{			printf("%d: %d\n",j,val[j]);			print(last[j]);		}	}		int getFail()	{		queue <int> q;		f[0]=0;		for (int c=0;c<26;c++)		{			int u=ch[0][c];			if (u)			{				f[u]=0;				q.push(u);				last[u]=0;			}		}				while (!q.empty())		{			int r=q.front(); q.pop();			for (int c=0;c<26;c++)			{				int u=ch[r][c];				if (!u) 				{					ch[r][c]=ch[f[r]][c];					continue;				}				q.push(u);				int v=f[r];				f[u]=ch[v][c];				last[u]=val[f[u]]?f[u]:last[f[u]];			}		}	}						void find(char *T)	{		int n=strlen(T);		int j=0;		for (int i=0;i<n;i++)		{			int c=idx(T[i]);			while(j&&!ch[j][c]) j=f[j];			j=ch[j][c];			if (val[j]) print(j);			else if (last[j]) print(last[j]);		}	}} tree;