검소한 검색

질의(query)가 주어지면 단어 모음에서 그 질의에 일치하는 단어 중 사전순으로 가장 앞서는(영어 사전에서 가장 먼저 나오는) 단어를 찾는 검색 엔진을 작성한다.

질의는 하나 이상의 항(term)을 세로 막대(|) 하나로 구분하여 나열한 것이다.

항은 하나 이상의 문자 뒤에 0개 이상의 부호 문자가 오는 형태이다. 부호 문자는 +s(양의 문자) 또는 -s(음의 문자)이며, 여기서 s는 한 개의 문자이다. 모든 문자는 소문자이고, 한 항 안에서 같은 문자가 두 번 이상 나타나지 않는다. 질의에는 공백이 없다. 항의 앞부분에 오는 부호 없는 문자들을 그 항의 무부호 문자라고 한다.

어떤 항이 한 단어와 일치하려면 다음을 모두 만족해야 한다.

• 단어가 그 항의 무부호 문자 중 적어도 하나를 포함하고,
• 단어가 그 항의 양의 문자를 모두 포함하며,
• 단어가 그 항의 음의 문자를 하나도 포함하지 않는다.

질의가 한 단어와 일치하려면 그 질의의 항 중 적어도 하나가 그 단어와 일치하면 된다.

입력은 하나 이상의 테스트 케이스로 이루어지며, 마지막에 #만 있는 줄이 와서 입력의 끝을 나타낸다.

각 테스트 케이스는 다음으로 구성된다.

• 각각 한 줄에 하나씩 놓인 1개 이상 100개 이하의 단어. 그 뒤에 단어 목록의 끝을 나타내는 *만 있는 줄;
• 각각 한 줄에 하나씩 놓인 하나 이상의 질의. 그 뒤에 테스트 케이스의 끝을 나타내는 **만 있는 줄.

각 단어는 1자 이상 20자 이하의 소문자로 이루어진다. 한 테스트 케이스 안의 모든 단어는 서로 다르다. 각 질의는 위 정의를 따르며 길이는 1자 이상 79자 이하이다.

각 질의에 대해, 그 테스트 케이스 안에서 질의에 일치하는 사전순으로 가장 앞서는 단어를 한 줄에 출력한다. 일치하는 단어가 없으면 NONE을 출력한다. 각 테스트 케이스의 모든 질의를 처리한 뒤에는 달러 기호($) 하나만 있는 줄을 출력한다.