문제

현대모비스는 자동차 부품 생산을 위한 개의 생산 공정이 가동되고 있다.

생산 공정은 개 이상, 개 이하의 유닛으로 구성되어 있으며, 한 공정 과정인 유닛은 알파벳 대문자로 표현한다.

부품이 생산되는 과정 중 이미 앞에서 불량이 나타난 경우 이후 공정을 거치더라도 제대로 된 부품이 만들어질 수 없다. 데이터사이언스팀에서는 불량 부품 생산으로 인한 피해를 최소화 하기 위해, 불량 부품이 생산될 수 있는 가능성이 있는 생산 공정을 찾는 연구를 진행하고 있다. 

데이터사이언스팀의 신입 개발자인 당신에게, 이러한 연구 결과를 토대로 불량 부품이 생산될 수 있는 생산 공정 중 가장 많은 곳이 어디인지 확인할 수 있는 프로그램의 개발이 과제로 주어졌다. 연구 결과는 알파벳 대문자로만 이루어진 개 이상, 개 이하의 문자열로 구성되어 있다.

불량 부품이 생산될 수 있는 생산 공정은 연구 결과로 시작하는 생산 공정을 뜻한다. 예를 들어 다음과 같이 개의 생산 공정이 있다고 가정해보자.

ABCD
AC
ABCD
ABD
AC
ABC
CABDE

만약 데이터사이언스팀에서 찾은 불량 부품이 생산될 수 있는 가능성이 있는 생산 공정이 AB라면, 전체 생산 공정 중 불량 부품이 생산될 수 있는 생산 공정은 ABCD, ABCD, ABD, ABC 총 4개이고, 그 중 가장 많은 생산 공정은 ABCD이다.

불량 부품이 생산될 수 있는 생산 공정 중, 가장 많은 개수의 생산 공정을 찾아보시오.

입력

첫째 줄에는 생산 공정의 수 이 주어진다.

둘째 줄부터 개의 줄에 걸쳐 생산 공정이 한 줄에 하나씩 주어진다. 각 생산 공정은 알파벳 대문자로만 이루어진 길이  이하의 문자열이다.

 번째 줄에는 연구 결과의 개수 이 주어진다.

 번째 줄부터 개의 줄에 걸쳐 연구 결과가 한 줄에 하나씩 주어진다.

각 연구 결과는 알파벳 대문자로만 이루어진 길이  이하의 문자열이다.

출력

주어지는 각 연구 결과의 답을 생산공정 개수의 형태로 한 줄에 하나씩 출력한다. 정답이 여러 개인 경우, 사전 순으로 가장 앞선 단어를 출력한다.

만약 해당 연구 결과에 해당하는 생산 공정이 없다면 을 출력한다.

구름 블로그 방문하기

* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.

* 문제에 대한 질문은 Q&A에 남겨주세요!