7. Ozajstné vzrušenie

Zdeno má veľmi rád vlaky. Raz sa takto premával celým Slovenskom – najprv Poprad, potom Žilina, následne Piešťany, Leopoldov, Trnava, až nakoniec vlak zastal v Bratislave. A potom opačným smerom – do Košíc. A zase naspäť. Zdeno celé dni nič iné nerobil, iba sa vozil vlakom z Košíc do Bratislavy a z Bratislavy do Košíc.

Počas svojich dobrodružstiev Zdeno poriadne vyhladol. Nemal inú možnosť, ako vystúpiť a kúpiť si bagetu v najbližšom stánku s občerstvením. Neuveríte, ale keď sa sýty Zdeno vracal na nástupište, nevedel si spomenúť, ktorým smerom išiel vlakom naposledy.

Zdeno si po toľkých cestách presne pamätá, ako vyzerá trasa z Bratislavy do Košíc – pamätá si ju ako postupnosť farieb domov, ktoré vidí z okna na severnej strane vlaku. (Zdeno vždy sedáva na severnej strane, aby mu nesvietilo slnko do očí.)

Pri svojej poslednej ceste sa Zdeno nepozeral z okna celý čas. Chvíľku sa pozeral, potom si prečítal noviny. Znova sa pár minút pozeral a zadriemal. A tak ďalej. Preto si pamätá len niekoľko súvislých úsekov trasy. Pomôžte mu na základe týchto spomienok zistiť, či cestuje z Bratislavy do Košíc, alebo opačným smerom.

Úloha

Daný je reťazec znakov, popisujúci farby domov na ceste z Bratislavy do Košíc. Zdeno rozoznáva 26 farieb, ktoré si označil písmenami a až z. Cesta z Košíc do Bratislavy vyzerá rovnako, len reťazec je obrátený (znaky čítame sprava doľava).

Ďalej máme niekoľko ďalších reťazcov, popisujúcich súvislé časti jazdy, ktoré si Zdeno pamätá. Časti sa neprekrývajú, môžu však na trase nasledovať aj hneď za sebou. Vlak cestuje z Bratislavy do Košíc, ak na ceste vieme nájsť všetky časti, a navyše v tom poradí, v akom sú časti zadané. Podobne to platí pre opačný smer, len časti hľadáme na opačnej ceste.

Zistite, ktorými smermi môže vlak cestovať.

Formát vstupu

Na prvom riadku vstupu je reťazec malých písmen anglickej abecedy – cesta z Bratislavy do Košíc. Na druhom riadku je číslo \(n\) – počet úsekov, ktoré Zdeno videl z okna vlaku.

Nasleduje \(n\) riadkov a na každom z nich je jeden reťazec malých písmen anglickej abecedy, popisujúci jeden úsek. Úseky sú dané v poradí, v akom ich Zdeno videl.

Súčet dĺžok všetkých reťazcov na vstupe nepresiahne \(2\,000\,000\).

Formát výstupu

Ak je jednoznačne určený smer jazdy, tak ak cestuje z Bratislavy do Košíc, vypíšte jeden riadok s textom “z Bratislavy do Kosic”, inak vypíšte “z Kosic do Bratislavy”.

Ak môže vlak cestovať oboma smermi, vypíšte “neviem”.

Ak vlak nemohol cestovať ani jedným smerom, vypíšte “zabludil”.

Príklad

Input:

abcaabbabaa
3
aab
ba
ba

Output:

neviem

Input:

xxyyzzxyzxyz
2
yyzz
zz

Output:

zabludil

Input:

cbaxxxxabcdefxxxxccbbaa
2
abc
xx

Output:

z Bratislavy do Kosic