Ключ до щоденника Магіки
Він розумний, він багатий — і йому потрібна ваша допомога. Перший цент Скруджа МакДака вкрадений Магікою де Спелл. Найкращі інспектори Скотланд-Ярду працюють над цією справою, але єдиний доказ, який вони знайшли, — це випадково загублений секретний щоденник Магіки. На жаль, він захищений якимось закляттям, яке заважає всім зрозуміти його зміст. Ось чому їм потрібні ви — найкращий математик Дакбурга.
Перше, що ви помітили, це те, що деякі слова зустрічаються набагато частіше за інші і утворюють дивний візерунок. Ви висунули гіпотезу, що ці слова є частиною закляття Магіки і вирішили ігнорувати їх для подальшого аналізу. Після цього стало досить очевидно, що деякі слова в щоденнику часто зустрічаються поруч одне з одним (наприклад, 'Scrooge' і 'McDuck'), тоді як інші розташовані досить незалежно одне від одного. Ви вважаєте, що це ключ до щоденника Магіки і хочете перевірити свою ідею.
Більш точно, слово — це непорожня безперервна послідовність англійських літер. Текст може містити інші символи, їх слід вважати пробілами. Слова вважаються нечутливими до регістру. Визначте 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}.