Ключ к дневнику Magica
Он умный, он богатый — и ему нужна ваша помощь. У Скруджа МакДака украли его первый десятицентовик, и это сделала Магика де Гипноз. Лучшие инспекторы Скотланд-Ярда работают над этим делом, но единственное доказательство, которое они нашли, — это случайно уроненный Магикой секретный дневник. К сожалению, он защищен каким-то заклинанием, которое не позволяет никому понять его содержание. Вот почему им нужны вы — лучший математик Дакбурга.
Первое, что вы заметили, это то, что некоторые слова встречаются гораздо чаще других и образуют какую-то странную закономерность. Вы выдвинули гипотезу, что эти слова являются частью заклинания Магики и решили игнорировать их для дальнейшего анализа. После этого стало довольно очевидно, что некоторые слова в дневнике часто встречаются рядом друг с другом (например, 'Скрудж' и 'МакДак'), в то время как другие слова расположены практически независимо друг от друга. Вы считаете, что это ключ к дневнику Магики и хотите проверить свою идею.
Более точно, слово — это непустая непрерывная последовательность английских букв. Текст может содержать другие символы, которые следует считать пробелами. Слова считаются нечувствительными к регистру. Определите P(a) как процент слова a в тексте (т.е. количество вхождений a, деленное на общее количество слов в тексте). Аналогично, определите P(a,b) как частоту вхождений слов a и b, расположенных рядом друг с другом (т.е. количество таких вхождений, деленное на общее количество пар соседних слов в тексте). Тогда
покажет вам, насколько зависимы слова a и b.
Вас особенно интересуют некоторые пары слов, и вы хотите проверить, насколько они зависимы. К сожалению, дневник слишком велик, чтобы делать этот анализ вручную, поэтому вы решили написать программу, чтобы сделать это за вас.
Входные данные
Первая строка ввода содержит одно целое число N — общее количество строк в дневнике Магики (1 ≤ N ≤ 4000). Затем следуют N строк текста. Дневник содержит только английские буквы, скобки, знаки препинания (0123456789.,:;-!?’()"), амперсанд и пробелы. Общая длина текста не превышает 500 КиБ, а длина каждого слова не более 20. Текст также содержит более одного немагического слова. N+2^ая строка содержит K — общее количество 'магических' слов, которые следует игнорировать (0 ≤ K ≤ 100). Следующие K строк содержат эти слова, по одному на строку, в нижнем регистре. N+K+3^я строка содержит Q — общее количество пар слов, которые вас интересуют (0 ≤ Q ≤ 50000). Затем следуют Q строк, каждая из которых содержит два слова в нижнем регистре.
Выходные данные
Для каждого запроса (a, b) вы должны вывести значение C(a, b) как число с плавающей точкой в отдельной строке с абсолютной или относительной точностью 10^{-6}.