Универсальная система ответов на вопросы
Каждому студенту нужна помощь в получении новых знаний через задавание вопросов. Опросы показывают, что некоторые похожие вопросы повторяются часто. Поэтому было бы полезно разработать автоматическую систему вопросов-ответов для ответа на эти вопросы. Ваш алгоритм не должен иметь предварительных знаний, но он должен уметь читать предложения и запоминать упомянутые факты. Всякий раз, когда задается вопрос о таком факте, система должна правильно на него ответить.
Входные данные
Входные данные состоят из множества диалогов.
На первой строке входных данных находится одно положительное целое число T. (T ≤ 500, но обратите внимание, что 95% из них относительно небольшие) Оно обозначает количество последующих диалогов. Каждый диалог включает одну или более строк. Каждая строка содержит одно предложение: либо утверждение, либо вопрос. Утверждения заканчиваются точкой (.), а вопросы — вопросительным знаком (?). После каждого диалога идет одна дополнительная строка. Эта строка заканчивается восклицательным знаком (!). Определения утверждений и вопросов будут обсуждены позже.
Предложения могут содержать слова, пробелы и знаки препинания. Все слова содержат только латинские буквы и чувствительны к регистру. В отличие от обычных правил английского письма, первая буква предложения должна оставаться строчной, если только первое слово само по себе не должно начинаться с заглавной буквы. Между словами нет лишних пробелов. Ни одно слово не будет иметь более 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?
Они являются вопросительной формой утверждений.
В каждом тестовом случае количество различных существительных фраз не превысит 100; количество различных глагольных фраз не превысит 100.
Выходные данные
Для каждого тестового случая выведите две строки. Первая строка описывает номер тестового случая, начиная с 1, а вторая строка содержит столько же символов, сколько вопросов в этом тестовом случае. Каждый символ — это либо 'Y' (обозначает, что вы можете логически получить этот факт), либо 'M' (иначе), без кавычек.