{"raw_statement":[{"iden":"statement","content":"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.\n\nMore 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 \n\nYou 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.\n\nFirst line of input contains one integer number N — the total number of lines in Magica's diary (1 ≤ N ≤ 4000). 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 500KiB, and the length of each word is not more than 20. The text also contains more than one non-magic word. N + 2nd line contains K — the total number of 'magic' words that should be ignored (0 ≤ K ≤ 100). Next K lines contain these words, one per line, lowercase. N + K + 3rd line contains Q — the total number of word pairs you're interested in (0 ≤ Q ≤ 50 000). Then Q lines follow, each containing two lowercase words.\n\nFor 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.\n\n"},{"iden":"input","content":"First line of input contains one integer number N — the total number of lines in Magica's diary (1 ≤ N ≤ 4000). 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 500KiB, and the length of each word is not more than 20. The text also contains more than one non-magic word. N + 2nd line contains K — the total number of 'magic' words that should be ignored (0 ≤ K ≤ 100). Next K lines contain these words, one per line, lowercase. N + K + 3rd line contains Q — the total number of word pairs you're interested in (0 ≤ Q ≤ 50 000). Then Q lines follow, each containing two lowercase words."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input3I have lived throughsome terrible things in my life,some of which actually happened.3ofinwhich3some actuallythings lifelived throughOutput6.5454545454545460.013.090909090909092Input1(2 - 2) Plus (1 - 1) equals 001equals plusOutput4.0"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T $ be the input text, consisting of $ N $ lines.  \nLet $ W $ be the multiset of all words in $ T $, where a word is a maximal contiguous sequence of English letters (case-insensitive).  \nLet $ M \\subseteq \\text{Words} $ be the set of $ K $ \"magic\" words to be ignored (given in lowercase).  \nLet $ W' = W \\setminus M $ be the filtered multiset of non-magic words.  \nLet $ n = |W'| $ be the total number of non-magic words.  \nLet $ P(a) = \\frac{\\text{count of } a \\text{ in } W'}{n} $ for any word $ a $.  \nLet $ P(a,b) = \\frac{\\text{number of adjacent pairs } (w_i, w_{i+1}) \\text{ in } W' \\text{ such that } \\{w_i, w_{i+1}\\} = \\{a,b\\}}{n-1} $ for any ordered pair $ (a,b) $ with $ a \\ne b $, and for $ a = b $, count unordered adjacent occurrences of $ a $ with itself.  \n\n**Constraints**  \n1. $ 1 \\le N \\le 4000 $  \n2. Total text length $ \\le 500 \\text{ KiB} $  \n3. Each word length $ \\le 20 $  \n4. $ 0 \\le K \\le 100 $, each magic word is lowercase  \n5. $ 0 \\le Q \\le 50000 $, each query is a pair of lowercase words  \n6. $ n > 1 $  \n\n**Objective**  \nFor each query $ (a, b) $, compute:  \n$$\nC(a,b) = \\frac{P(a,b)}{P(a) \\cdot P(b)}\n$$  \nOutput $ C(a,b) $ as a floating-point number with absolute or relative error $ \\le 10^{-6} $.","simple_statement":"Given a text, extract all words (sequences of letters, case-insensitive). Ignore a list of \"magic\" words. For each query pair (a, b), compute the conditional probability:  \nP(b | a) = (number of times \"a\" is immediately followed by \"b\") / (number of times \"a\" appears).  \nOutput the result for each query with precision 1e-6.","has_page_source":false}