Draganče radi za kontraobaveštajnu službu. On je otkrio da se šifrovane poruke neprijatelja uvek dobijaju linearnim preslikavanjem. Najpre se svako slovo predstavi brojem od 0 do n - 1, gde je n broj slova u pismu (ove brojeve ćemo zvati indeksima slova). Potom se šifra zada u obliku y = (a +b · x) mod n, gde je nzd(b, n) = 1. To znači da se slovo predstavljeno brojem x šifrira slovom koje je predstavljeno brojem y (y = (a + b · x) mod n). Pored saznanja o načinu šifrovanja poruka, Draganče ima i podatke o učestanosti svih slova u jeziku neprijatelja. Za svako slovo x se zna očekivani procenat pojavljivanja p(x) u proizvoljnom tekstu. Treba pomoći Dragančetu da dešifruje jednu izuzetno važnu poruku uz pomoć statistike i saznanja o linearnom šifrovanju.  Potrebno je izvršiti dešifrovanje tako da se statistika u dobijenom tekstu što više poklapa sa očekivanom statistikom. Kvalitet poklapanja za odredjeno slovo se meri tako što se najpre izračuna učestanost tog slova u dešifrovanom tekstu dc(x) (broj pojavljivanja slova x podeljen sa ukupnim brojem slova u tekstu). Potom se kvalitet poklapanja q(x) računa kao (p(x)-dc(x))². Kvalitet poklapanja čitavog dešifrovanog teksta se računa kao suma kvaliteta poklapanja svih slova.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu se nalazi prirodan broj n, 3 ≤ n ≤ 26, ukupan broj slova u neprijateljskom alfabetu. Sledi n redova i u svakom je dato jedno slovo iz alfabeta i jedan broj, razdvojeni razmakom. Slovo u prvom redu ima indeks 0, u drugom 1, ... u n-tom redu ima indeks n - 1. Slovo je uvek predstavljeno kao veliko slovo iz engleskog alfabeta, dok broj predstavlja procenat učestanosti datog slova u proizvoljnom tekstu. Procenat je zadat sa dve decimale. Slovo imaju različite učestanosti, a ukupan zbir svih učestanosti je 100. U sledećem redu je ceo broj L (10 ≤ L ≤ 1000) i on predstavlja dužinu šifrovanog teksta. U poslednjem redu, nalazi se tekst od tačno L slova (bez razmaka i znakova interpunkcije) koji predstavljaju šifrovani tekst. Sva slova koja se nalaze u šifrovanom tekstu su prethodno već zadata sa svojim učestanostima.

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U jedinom redu izlaza treba ispisatidešifrovani tekst, dešifrovan preko linearnog preslikavanja,a koji najviše odgovara zadatoj statistici.

Primer 1.

4
B 42.25
A 20.00
Z 10.15
E 27.60
8
AZABAZEBAZ

BEBABEZABE

Napomena.

Na osnovu ulaza imamo se slova predstavljaju brojevima od 0do 3 na sledeći nachin: B → 0, A → 1, Z → 2 i E →3. Preslikavanje kod kog se dobija najbolje preklapanje je y =(a + b · x) mod 4, gde su a = 1 i b = 3.