Magica`nın gündəliyinin açarı
O, ağıllıdır, o, varlıdır — və sizin köməyinizə ehtiyacı var. Scrooge McDuck-un Bir Nömrəli Qəpiyi Magica De Spell tərəfindən oğurlanıb. Scotland Yard-ın ən yaxşı müfəttişləri bu iş üzərində çalışırlar, lakin əldə etdikləri yeganə sübut Magica-nın təsadüfən düşürdüyü gizli gündəlikdir. Təəssüf ki, bu gündəlik hər kəsin məzmununu başa düşməsinə mane olan bir sehrlə qorunur. Buna görə də, Duckburg-un ən yaxşı riyaziyyatçısı olan sizə ehtiyac duyurlar.
İlk diqqətinizi çəkən şey bəzi sözlərin digərlərindən daha çox təkrarlanması və qəribə bir naxış yaratmasıdır. Siz bu sözlərin Magica-nın sehrinin bir hissəsi olduğunu fərz etdiniz və gələcək analiz üçün onları nəzərə almamağa qərar verdiniz. Bundan sonra gündəlikdə bəzi sözlərin bir-birinin yanında çox tez-tez tapıldığı (məsələn, 'Scrooge' və 'McDuck' kimi) digərlərinin isə bir-birindən müstəqil yerləşdiyi aydın oldu. Siz bunun Magica-nın gündəliyinin açarı olduğuna inanırsınız və fikrinizi yoxlamaq istəyirsiniz.
Daha dəqiq desək, söz boş olmayan ardıcıl İngilis hərflərindən ibarət bir sıra kimi qəbul edilir. Mətn digər simvolları da ehtiva edə bilər, onları boşluq kimi qəbul etməlisiniz. Sözlər böyük-kiçik hərf fərqinə həssas deyil. P(a) sözünün mətn içindəki faizini təyin edin (yəni, a sözünün təkrarlanma sayını mətn içindəki ümumi söz sayına bölünməsi). Eyni şəkildə, P(a,b) sözlərinin bir-birinə bitişik olma faizini təyin edin (yəni, bu cür təkrarlanma sayını mətn içindəki ümumi bitişik söz cütlərinin sayına bölünməsi). Sonra
sizə a və b sözlərinin nə qədər asılı olduğunu göstərəcək.
Xüsusilə bəzi söz cütləri ilə maraqlanırsınız və onların nə qədər asılı olduğunu yoxlamaq istəyirsiniz. Təəssüf ki, gündəlik çox böyükdür və bu analizi əl ilə etmək mümkün deyil, buna görə də bunu sizin üçün edəcək bir proqram yazmağa qərar verdiniz.
Giriş verilənləri
Girişin ilk sətri Magica-nın gündəliyindəki sətirlərin ümumi sayını göstərən bir tam ədəd N ehtiva edir (1 ≤ N ≤ 4000). Sonra N sətir mətn gəlir. Gündəlik yalnız İngilis hərfləri, mötərizələr, durğu işarələri (0123456789.,:;-!?’()"), ampersandlar və boşluqlar ehtiva edir. Mətnin ümumi uzunluğu 500 KiB-dən çox deyil və hər sözün uzunluğu 20-dən çox deyil. Mətn həmçinin bir neçə sehrli olmayan söz ehtiva edir. N+2^ci sətir K — nəzərə alınmamalı olan 'sehrli' sözlərin ümumi sayını ehtiva edir (0 ≤ K ≤ 100). Növbəti K sətir bu sözləri ehtiva edir, hər biri bir sətirdə, kiçik hərflərlə. N+K+3^cü sətir Q — maraqlandığınız söz cütlərinin ümumi sayını ehtiva edir (0 ≤ Q ≤ 50000). Sonra Q sətir gəlir, hər biri iki kiçik hərfli söz ehtiva edir.
Çıxış verilənləri
Hər sorğu üçün (a, b) C(a, b) dəyərini ayrıca sətirdə 10^{-6} dəqiqliyi ilə ondalık nöqtə ilə çıxarmalısınız.