program poj1318;
type
     pointer2=^node2;
     node2=record
       next:pointer2;
       word:string;
     end;
     pointer1=^node1;
     node1=record
       next:array[1..26] of pointer1;
       rootOfList:pointer2;
     end;
var s0,s:string;
    root,p:pointer1;
    q1,q2:pointer2;
    t:longint;
procedure Initialize;
begin
    new(root);
    fillchar(root^.next,sizeof(root^.next),0);
    root^.rootOfList:=nil;
end;
procedure sort;
var tmp:char;
    i,j:longint;
begin
    for i:=1 to length(s) do
    for j:=1 to length(s)-1 do
      if s[j]>s[j+1] then
        begin
          tmp:=s[j];
          s[j]:=s[j+1];
          s[j+1]:=tmp;
        end;
end;
procedure Insert;
var i:longint;
begin
    p:=root;
    for i:=1 to length(s) do
      begin
        t:=ord(s[i])-96;
        if p^.next[t]=nil then
          begin
            new(p^.next[t]);
            fillchar(p^.next[t]^.next,sizeof(p^.next[t]^.next),0);
            p^.next[t]^.rootOfList:=nil;
          end;
        p:=p^.next[t];
      end;
    if p^.rootOfList=nil then
      begin
        new(p^.rootOfList);
        p^.rootOfList^.word:=s0;p^.rootOfList^.next:=nil;
        exit;
      end;
    q1:=p^.rootOfList;
    while (q1<>nil) and (s0>q1^.word) do
      begin
        q2:=q1;
        q1:=q1^.next;
      end;
    if q1=nil then
      begin
        new(q1);
        q1^.word:=s0;q1^.next:=nil;q2^.next:=q1;
      end
    else if q1=p^.rootOfList then
      begin
        new(q2);
        p^.rootOfList:=q2;
        q2^.word:=s0;q2^.next:=q1;
      end
    else
      begin
        new(q2);
        q2^.word:=s0;q2^.next:=q1^.next;
        q1^.next:=q2;
      end;
end;
procedure Failure;
begin
     writeln('NOT A VALID WORD');
     writeln('******');
end;
procedure QuerynPrint;
var i:longint;
begin
    p:=root;
    for i:=1 to length(s) do
      begin
        t:=ord(s[i])-96;
        if p^.next[t]=nil then
          begin
            Failure;
            exit;
          end;
        p:=p^.next[t];
      end;
    if p^.rootOfList=nil then
      begin
        Failure;
        exit;
      end;
    q1:=p^.rootOflist;
    while q1<>nil do
      begin
        writeln(q1^.word);
        q1:=q1^.next;
      end;
    writeln('******');
end;
begin
    Initialize;
    readln(s);
    while s<>'XXXXXX' do
      begin
        s0:=s;
        sort;
        Insert;
        readln(s);
      end;
    readln(s);
    while s<>'XXXXXX' do
      begin
        sort;
        QuerynPrint;
        readln(s);
      end;
end.