단어 애너그램 찾기

미국 전역의 수많은 신문에는 Jumble이라는 단어 게임이 실려 있습니다. 이 게임의 목표는 수수께끼를 푸는 것이지만, 정답에 들어갈 글자들을 알아내려면 먼저 뒤섞인 단어들을 원래대로 되돌려야 합니다. 여러분이 할 일은 뒤섞인 단어를 복원하는 프로그램을 작성하는 것입니다.

입력은 네 부분으로 이루어집니다.

1. 사전: 한 줄에 한 단어씩, 최소 1개에서 최대 100개의 단어가 주어집니다.
2. XXXXXX만 있는 줄: 사전의 끝을 나타냅니다.
3. 복원해야 할 뒤섞인 '단어'들: 각 단어가 한 줄에 하나씩, 한 개 이상 주어집니다.
4. XXXXXX만 있는 줄: 입력의 끝을 나타냅니다.

사전 단어와 뒤섞인 단어를 포함한 모든 단어는 소문자 영어 알파벳으로만 이루어지며, 길이는 1자 이상 6자 이하입니다. (종료 표시 XXXXXX는 대문자 X로 이루어져 있음에 유의하세요.) 사전은 정렬되어 있지 않을 수 있으나, 사전에 있는 각 단어는 서로 중복되지 않습니다.

입력의 각 뒤섞인 단어에 대해, 그 글자들을 재배열하여 만들 수 있는 모든 사전 단어를 사전순으로 출력합니다. 이 목록의 각 단어는 한 줄에 하나씩 출력합니다. 만들 수 있는 사전 단어가 없어 목록이 비어 있으면, 대신 NOT A VALID WORD 한 줄을 출력합니다. 두 경우 모두, 목록의 끝을 나타내기 위해 별표 여섯 개(******)로 이루어진 줄을 출력합니다.