단어 만들기

3×3 퍼즐판에는 각 칸마다 영어 대문자 하나가 놓여 있다. 퍼즐판의 글자들을 사용해 사전에 있는 단어를 만들 수 있다. 단어는 4글자 이상이어야 하며, 각 칸의 글자는 최대 한 번만 사용할 수 있으므로 같은 문자는 퍼즐판에 있는 개수만큼만 사용할 수 있다. 또한 가운데 칸에 놓인 글자는 반드시 단어에 포함되어야 한다.

퍼즐판에 사용할 9개의 문자는 이미 정해져 있지만, 어느 글자를 가운데에 놓을지는 아직 정해지지 않았다. 가운데 글자를 무엇으로 정하느냐에 따라 만들 수 있는 단어의 수가 달라진다.

사전과 여러 퍼즐판이 주어졌을 때, 각 퍼즐판마다 가운데 글자로 선택하면 만들 수 있는 단어 수가 가장 적어지는 문자들과 그 개수, 그리고 가장 많아지는 문자들과 그 개수를 구하라.

먼저 사전을 이루는 단어들이 한 줄에 하나씩 주어진다. 단어는 최대 200,000개이며, 각 단어는 4글자 이상 9글자 이하의 영어 대문자로만 이루어져 있다. 단어들은 사전순으로 정렬되어 있다. 사전의 끝은 - 한 줄로 표시된다.

그다음 여러 개의 퍼즐판이 주어진다. 각 퍼즐판은 9개의 영어 대문자로 이루어진 문자열 한 줄이다. 전체 입력의 끝은 # 한 줄로 표시된다.

각 퍼즐판마다 다음 네 값을 공백으로 구분해 한 줄에 출력한다.

1. 만들 수 있는 단어 수가 최소가 되도록 가운데에 놓을 수 있는 문자들을 알파벳순으로 이어 쓴 문자열
2. 그 최소 단어 수
3. 만들 수 있는 단어 수가 최대가 되도록 가운데에 놓을 수 있는 문자들을 알파벳순으로 이어 쓴 문자열
4. 그 최대 단어 수

같은 최솟값 또는 최댓값을 만족하는 문자가 여러 개이면 중복 없이 알파벳순으로 모두 출력한다. 퍼즐판에 같은 문자가 여러 번 있어도 출력에는 한 번만 포함한다.