Mirko i Slavko igraju sledeću igru: Mirko počinje igru zamišljanjem neke reči. Međutim, on ne kaže Slavku koju je reč zamislio, već mu kaže samo prvo slovo te reči. Sada Slavko zamišlja reč koja počinje slovom koje je Mirko rekao i kaže Mirku prva dva slova svoje reči. Mirko sada opet zamišlja reč koja počinje slovima koje je Slavko rekao (nova reč može, ali i ne mora biti reč koju je na početku zamislio) i kaže Slavku prva tri slova. Ova procedura se nastavlja sve dok slova koja kaže Mirko ili Slavko ne formiraju kompletnu reč. Igrač koji prvi formira kompletnu reč je izgubio igru. To znači iako je Mirko, na primer, zamislio reč 'lepota' i kaže Slavku prva četiri slova 'lepo' - on gubi, jer je reč 'lepo' takođe reč srpskog jezika.

Kako bi igra bila ravnopravna, oba igrača mogu iskoristiti samo reči iz unapred definisanog rečnika. Ako oba igrača igraju optimalno, tada je moguće odrediti ko će na kraju igre biti pobednik. Optimalno igranje podrazumeva da svaki od igrača nastoji da dobije igru u što je moguće manje poteza (znajuči da će i njegov protivnik takođe igrati optimalno); ukoliko igrač ne može da dobije igru, onda želi da izgubi što je moguće kasnije.

Krajnji ishod igre je reč iz rečnika koju kaže igrač koji gubi. Ako u nekom momentu nije bitno za dalji razvoj igre koje slovo će igrač odabrati - on bira uvek slovo koje dolazi ranije u engleskoj abecedi (leksikografski najmanje). Odrediti koji igrač pobeđuje u ovoj igri i reč kojom se igra završava.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu se nalazi prirodni broj n (1 ≤n ≤ 5000). U sledećih n redova se nalazi po jedna reč sastavljena od malih slova engleske abecede, dužine manje ili jednake od 50, koja predstavlja reč iz zajedničkog rečnika za oba igrača.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom redu ispisati koji igrač pobeđuje (1 za Mirka i 2 za Slavka), a u drugom redu ispisati reč kojom se igra završava, ako oba igrača igraju optimalno.

Primer 1:

8
avioni
banana
berza
selo
seobe
kosa
kola
kuca

1
kola

Objašnjenje.

Ako Mirko kaže slovo 'b', tada će Slavko pobediti biranjem reči 'berza' tako što kaže slovo 'e'. Mirko pobeđuje ako zamisli bilo koju reč na 'a', 'k' ili 's'. Ako bi odabrao reč 'avioni' pobedio bi u šest poteza, dok u ostalim slučajevima (ako izabere prvo slovo 's' ili 'k') pobeđuje u 4 poteza. Mirko bira slovo 'k' jer je leksikografski manje od 's'. Zatim Slavko bira slovo 'o', pa onda Mirko slovo 'l' (zato sto 'l' dolazi pre 's' po leksikografskom uređenju) i Slavko slavko na kraju bira slovo 'a'. Dakle, pobeđuje Mirko (prvi igrač), a tražena reč na kraju igre je 'kola'.

Primer 2:

3
zzz
zzza
ttt

2
ttt