만능 질의응답 시스템

학생들은 질문을 던지며 끊임없이 새로운 지식을 얻는다. 조사에 따르면 서로 비슷한 질문이 반복해서 자주 나온다고 한다. 그래서 이런 질문에 자동으로 답해 주는 시스템을 만들면 유용하다. 이 프로그램은 사전 지식이 전혀 없는 상태에서 시작하지만, 문장을 읽어 그 안에 서술된 사실을 기억하고, 그 사실에 대한 질문이 들어오면 올바르게 답해야 한다.

입력은 여러 개의 대화(dialogue)로 이루어진다.

첫 줄에는 양의 정수 $T$ 하나가 주어진다($T \le 500$이며, 그중 약 95%는 비교적 작다). 이는 뒤따르는 대화의 개수이다. 각 대화는 한 줄 이상으로 이루어지고, 각 줄에는 문장이 정확히 하나씩 들어 있으며 이 문장은 서술문(statement) 또는 질문(question)이다. 서술문은 마침표(.)로 끝나고, 질문은 물음표(?)로 끝난다. 각 대화 뒤에는 느낌표(!)로 끝나는 줄이 하나 더 있으며, 이 줄은 대화의 끝을 표시할 뿐이다.

문장은 단어, 공백, 문장부호로 이루어질 수 있다. 모든 단어는 라틴 문자만으로 이루어지며 대소문자를 구분한다. 일반적인 영어 표기 규칙과 달리, 첫 단어 자체가 대문자로 시작해야 하는 경우가 아니라면 문장의 첫 글자는 소문자로 둔다. 단어 사이에 불필요한 공백은 없다. 어떤 단어도 10글자를 넘지 않는다. 한 대화의 줄 수는 최대 1000개이다.

서술문

각 서술문은 다음 형식 중 하나이다.

noun_phrase are noun_phrase.
noun_phrase can verb_phrase.
everything which can verb_phrase can verb_phrase.
everything which can verb_phrase are noun_phrase.

noun_phrase와 verb_phrase는 각각 한 단어이다. 네 형식의 의미는 다음과 같다.

A are B: X가 A이면, X는 B이다.
A can B: X가 A이면, X는 B할 수 있다.
everything which can A can B: X가 A할 수 있으면, X는 B할 수 있다.
everything which can A are B: X가 A할 수 있으면, X는 B이다.

질문

각 질문은 다음 형식 중 하나이다.

are noun_phrase noun_phrase?
can noun_phrase verb_phrase?
can everything which can verb_phrase verb_phrase?
are everything which can verb_phrase noun_phrase?

이들은 위 네 서술문에 대응하는 질문 형태이며, 각 질문은 해당 사실이 같은 대화에서 지금까지 주어진 서술문들로부터 논리적으로 유도될 수 있는지를 묻는다.

각 대화에서 서로 다른 noun_phrase의 개수는 최대 100개, 서로 다른 verb_phrase의 개수는 최대 100개이다.

각 대화마다 두 줄을 출력한다. 첫 줄은 Case #k:이며 k는 1부터 세는 대화 번호이다. 둘째 줄에는 그 대화의 질문마다 한 글자씩 질문 순서대로 출력한다. 해당 사실을 논리적으로 유도할 수 있으면 Y, 그렇지 않으면 M을 쓴다. 대화에 질문이 하나도 없으면 둘째 줄은 빈 줄이다.