#include<stdio.h>
#include<string.h>
bool hash[1080];
char str2[1080][51];
int rank[20001];
char ranklist[20001][51];
char stack[1007][51];
int snum;
int r;
struct D
{
	int flag;
	D* next[26];
	char str[51];
}*dic[26];
int init(D *d)
{
	for(int i=0;i<=25;i++)
		d->next[i]=NULL;
	d->flag=0;
	return 0;
}
int in(char *str)
{
	int i;
	int value=0;
	for(i=0;str[i]!=0;i++)
	{
		value*=26;
		value+=str[i]-'a';
		value%=1080;
	}
	while(hash[value]!=0&&strcmp(str,str2[value])!=0)
	{
		value++;
		value%=1080;
	}
	if(hash[value]==0)
	{
		hash[value]=1;
		strcpy(str2[value],str);
		return 0;
	}
	else
	{
		return 1;
	}
	return 0;
}
int putrank(char *str)
{
	int i;
	int value=0;
	for(i=0;str[i]!=0;i++)
	{
		value*=26;
		value+=str[i]-'a';
		value%=20000;
	}
	while(rank[value]!=0&&strcmp(ranklist[value],str)!=0)
	{
		value++;
		value%=20000;
	}
	rank[value]=++r;
	strcpy(ranklist[value],str);
	return 0;
}
int putin(char *str)
{
	int i;
	putrank(str);
	if(dic[str[0]-'a']==NULL)
	{
		dic[str[0]-'a']=new D;
		init(dic[str[0]-'a']);
	}
	D *p=dic[str[0]-'a'];
	for(i=1;str[i]!='\0';i++)
	{
		if(p->next[str[i]-'a']==NULL)
		{
			p->next[str[i]-'a']=new D;
			init(p->next[str[i]-'a']);
		}
		p=p->next[str[i]-'a'];
	}
	p->flag=1;
	memcpy(p->str,str,sizeof(str));
	return 0;
}
int check(char *str)
{
	D *p=NULL;
	int j;
	int flag=0;
	int f;
	flag=0;
	f=1;
	for(j=0;str[j]!=0;j++)
	{
		if(flag==0)
		{
			p=dic[str[j]-'a'];
			flag=1;
		}
		else
			p=p->next[str[j]-'a'];
		if(p==NULL)
		{
			f=0;
			break;
		}
	}
	if(p!=NULL&&f==1&&p->flag==1)
	{
		return 1;
	}
	return 0;
}
int delet(char *str)
{
	int i,j;
	char str1[51];
	int len1=0;
	for(i=0;str[i]!=0;i++)
	{
		len1=0;
		for(j=0;str[j]!=0;j++)
		{
			if(j==i)
				continue;
			str1[len1++]=str[j];
		}
		str1[len1]=0;
		if(!in(str1)&&check(str1))
			strcpy(stack[++snum],str1);
	}
	return 0;
}
int change(char *str)
{
	int i,k;
	char str1[51];
	for(i=0;str[i]!=0;i++)
	{
		strcpy(str1,str);
		for(k=0;k<=25;k++)
		{
			str1[i]=k+'a';
			if(!in(str1)&&check(str1))
				strcpy(stack[++snum],str1);
		}
	}
	return 0;
}
int insert(char *str)
{
	D *p;
	int i,m;
	int j,k;
	int flag=0;
	int f,step;
	int len=strlen(str);
	char str1[51];
	str[len+1]=0;
	int len1=0;
	for(i=0;i<=len;i++)
	{
		f=0;
		len1=0;
		for(j=0;j<=len;j++)
		{
			if(j==i)
			{
				f=1;
				for(k=0;k<=25;k++)
				{
					len1=j;
					str1[len1++]=k+'a';
					for(m=j;m<=len;m++)
					{
						str1[len1++]=str[m];
					}
					str1[len1]=0;
					if(!in(str1)&&check(str1))
						strcpy(stack[++snum],str1);
				}
			}
			str1[len1++]=str[j];
			if(f==1)
				break;
		}
	}
	return 0;
}
int getrank(char *str)
{
	int i;
	int value=0;
	for(i=0;str[i]!=0;i++)
	{
		value*=26;
		value+=str[i]-'a';
		value%=20000;
	}
	while(rank[value]==0||strcmp(ranklist[value],str)!=0)
	{
		value++;
		value%=20000;
	}
	return rank[value];
	
}
int sor()
{
	int i,j,array[1080];
	char str[51];
	for(i=1;i<=snum;i++)
		array[i]=getrank(stack[i]);
	for(i=1;i<=snum;i++)
		for(j=i+1;j<=snum;j++)
		{
			if(array[i]>array[j])
			{
				int temp=array[i];
				array[i]=array[j];
				array[j]=temp;
				strcpy(str,stack[i]);
				strcpy(stack[i],stack[j]);
				strcpy(stack[j],str);
			}
		}
		for(i=1;i<=snum;i++)
			printf(" %s",stack[i]);
		return 0;
}
int find(char *str)
{
	if(check(str))
	{
		printf("%s is correct\n",str);
		return 0;
	}
	printf("%s:",str);
	delet(str);
	change(str);
	insert(str);
	sor();
	printf("\n");
	return 0;
}
int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	char str[51];
	int flag=0;
	for(int i=0;i<=25;i++)
		dic[i]=NULL;
	memset(rank,0,sizeof(rank));
	r=0;
	while(scanf("%s",str)!=EOF)
	{
		if(str[0]=='#')
		{
			if(flag==0)
				flag=1;
			else
				break;
			continue;
		}
		if(flag==0)
		{
			putin(str);
		}
		if(flag==1)
		{
			r=0;
			memset(hash,0,sizeof(hash));
			snum=0;
			find(str);
		}
	}
	return 0;
}