eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Key to Magica`s diary

Key to Magica`s diary

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

He’s smart, he’s rich — and he needs your help. Scrooge McDuck’s Number One Dime is stolen by Magica De Spell. Best Scotland Yard inspectors are working on this case but the only evidence they found is Magica’s accidentally dropped secret diary. Unfortunately, it is protected by some spell that prevents everybody from understanding its contents. That’s why they need you - the best mathematician of Duckburg.

The first thing you noticed is that some words are occurring much more often than others and form some weird pattern. You’ve made a hypothesis that these words are part of Magica’s spell and decided to ignore them for future analysis. After that it became pretty obvious that some words in the diary are found next to each other quite often (such as ’Scrooge’ and ’McDuck’) while others will be located pretty much independent from each other. You believe that this is the key to Magica’s diary and want to check your idea.

More precisely, word is a non-empty continuous sequence of English letters. Text may contain other symbols, you should consider them as spaces. Words are considered to be case-insensitive. Define P(a) as percentage of word a in the text (i.e. the number of a occurrences divided by the total number of words in the text). Similarly, you define P(a,b)as the rate of words a and b occurrences adjacent to each other (i.e. number of such occurrences divided by total number of adjacent word pairs in the text). Then

will show you how dependent words a and b are.

You are particularly interested in some pairs of words and want to check how dependent they are. Unfortunately, the diary is too large to do this analysis manually, so you decided to write a program to do that for you.

Вхідні дані

First line of input contains one integer number N — the total number of lines in Magica’s diary (1N4000). Then N lines of text follow. Diary contains only English letters, brackets, punctuation marks (0123456789.,:;-!?’()"), ampersands and spaces. The total length of the text is less or equal than 500 KiB, and the length of each word is not more than 20. The text also contains more than one non-magic word. N+2^nd line contains K — the total number of 'magic' words that should be ignored (0K100). Next K lines contain these words, one per line, lowercase. N+K+3^rd line contains Q — the total number of word pairs you're interested in (0Q50000). Then Q lines follow, each containing two lowercase words.

Вихідні дані

For each query (a, b) you should output the value of C(a, b) as a floating point number on the separate line with absolute or relative precision of 10^{-6}.

Приклад

Вхідні дані #1
3
I have lived through
some terrible things in my life,
some of which actually happened.
3
of
in
which
3
some actually
things life
lived through
Вихідні дані #1
6.545454545454546
0.0
13.090909090909092
Джерело ACM ICPC 2012-2013, NEERC, Moscow Subregion, Moscow, Sunday, October 21, 2012