#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef struct hehe
{
	string str;
	struct hehe* next;
	
}Myhash;

struct mycmp
{
	bool operator ()(string a,string b)
	{
		int i=0;
		while(a[i]==b[i])
		{
			i++;
		}
		return a[i]>b[i];

	}
};
priority_queue<string,vector<string>, mycmp >mq;
Myhash myhash[101];
void add_hash(string str)
{
	int key=0;
	for(int i=0;i<str.size();i++)
		key+=str[i]-'a';
	key=key%101;
	Myhash* temp=new Myhash();
	temp->str=str;
	temp->next=myhash[key].next;
	myhash[key].next=temp;
}
void find_hash(string str)
{
	
	int key=0;
	for(int i=0;i<str.size();i++)
		key+=str[i]-'a';
	key=key%101;
	Myhash* temp=myhash[key].next;
	int len=str.size();
	bool flag=false;
	while(temp!=NULL)
	{
		if(len!=temp->str.size())
		{
			temp=temp->next;
			continue;
		}
		else
		{
			string pstr=temp->str;
			int i=1;
			while(i<1000)
			{
				if(str==pstr)
				{
					flag=true;
					mq.push(pstr);
					
					break;
				}
				next_permutation(str.begin(),str.end());
				i++;
			}
		}
		temp=temp->next;
	}
	if(flag==false)
		cout<<"NOT A VALID WORD"<<endl;
	else
	{
		while(mq.empty()==false)
		{
			cout<<mq.top()<<endl;
			mq.pop();
		}
		
	}
	cout<<"******"<<endl;
}
int main()
{
	string str;
	int key;
	while(cin>>str&&str!="XXXXXX")
	{		
		add_hash(str);
	}
	while(cin>>str&&str!="XXXXXX")
	{
		
		find_hash(str);
	}
	return 0;
}