Boggle

상근이는 보드 게임 "Boggle"을 아주 좋아한다. Boggle은 글자가 적힌 주사위 16개를 4×4 격자에 늘어놓고, 그 안에서 단어를 최대한 많이 찾는 게임이다.

상근이는 부인을 Boggle로 이겨본 적이 한 번도 없다. 질 때마다 쓰레기 버리기나 설거지 같은 집안일을 떠맡는다. 그래서 이번에는 프로그램을 짜서 이겨보려고 한다.

단어는 가로, 세로, 대각선으로 인접한 칸을 차례대로 이어서 만든다. 단, 한 칸은 한 단어에 한 번만 쓸 수 있다. 사전에 실려 있는 단어만 올바른 단어로 인정한다.

점수는 단어의 길이에 따라 매긴다. 1글자와 2글자는 0점, 3글자와 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 한 보드의 점수는 그 보드에서 찾은 단어의 점수를 모두 더한 값이다.

사전에 실린 단어 목록과 Boggle 보드가 주어진다. 보드마다 얻을 수 있는 최대 점수와 가장 긴 단어, 찾은 단어의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 사전에 들어 있는 단어의 수 $w$가 주어진다. ($1 < w < 300{,}000$)

다음 $w$개 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져 있고, 길이는 8 이하이다. 사전이 끝나면 빈 줄이 하나 나온다.

그 다음 줄에는 보드의 개수 $b$가 주어진다. ($1 < b < 30$) 각 보드는 알파벳 대문자 4개로 이루어진 줄 4개로 주어지고, 보드와 보드 사이에는 빈 줄이 하나 있다.

보드마다 한 줄에 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 공백으로 구분해 출력한다.

한 보드에서 같은 단어를 여러 경로로 찾더라도 한 번만 센다. 가장 긴 단어가 여럿이면 사전 순으로 앞서는 것을 출력한다. 찾을 수 있는 단어가 적어도 하나 있는 보드만 입력으로 주어진다.