def defusc(s):
    return ''.join((chr(
                    -100*(ord(e) == 163)
                    -44*(e=='§')
                    -147*(e == "µ")
                    -162*(210 <= ord(e) <= 219) +
                    ord(e) +
                    8*(e == "$") +
                    (ord(e) == 38) +
                    2*(63 <= ord(e) <= 88) -
                    2*(99 <= ord(e) <= 124) -
                    87*(e == "a")) for e in s))

exec(defusc(''.join(["htqo dtqyugt korqtv fqewogpv$ jvonaaurcotgcfgt = [[&ÔÔÖÒØÛÛÓ",
"&$ &@?RGQR?&$ &ÓÛ&$ &@tcxq !&]$a[&ÔÔÖÓÓÛÔÓ&$ &&$ &&$ &&]$a[&",
"ÔÔÖÒÚÚÕÔ&$ &@MCA?QQC-D?PGEMSV&$ &ÓÖ&$ µAgnc xcwv rnwu swg çc",
" gp n&évcv. Kcku lg p&ck rcu cwvqtkué à ejctigt wpg fgwzkèog",
" xgtukqp crtèu (qw xgtu ng hkp) fw eqwtu.µ]$a[&ÔÔÖÒÕ×ÔÚ&$ &A",
"?QQGCP&$ &ÓÚ&$ µA&guv fw vtèu dqp vtcxckn$ xqwu cxg| eqortku",
" dgcweqwr fg ejqugu ! Hg rgpug swg xqwu rqwttkg| chhkpgt ngu",
" hqtogu gv ngu cttqpfku$ rqwt wp tgpfw oqkpu rncuvkswg oqwné",
"µ]$a[&ÔÔÖÒÖÚÕ×&$ &AJ?P? QGKMCQ&$ &ÓÖ$×&$ µTqwu cxg| fgu rtqd",
"nèogu f&qodtcigu swk ug téingtckgpv cxge fgu xgtvkegu clqwvé",
"u jqtk|qpvcngogpv (evtng P). @kgp nc rqkipég !µ]$a[&ÔÔÖÒÔÙÔ×",
"&$ &BSKMLR&$ &ÓØ&$ &@qp vtcxckn ! Ncuug| egtvckpu énéogpvu g",
"p oqfg uoqqvj gv hckvgu wp dgn éencktcig.&]$a[&ÔÔÖÒÖÓÙÙ&$ &B",
"SPAFML&$ &ÓØ&$ µA&guv fw dqp vtcxckn. Hg rgpug sw&kn hcwftck",
"v$ rqwt ng tgpfw hkpcn$ guuc{gt fg vtqwxgt wpg hqtog rnwu rc",
"tvkewnkètg à egvvg iqwtfg.µ]$a[&ÔÔÖÒØ×××&$ &CQR?@JCR&$ &ÓÙ&$",
" &Sp dqp vtcxckn$ qtkikpcn. Gn hcwv rcuugt egtvckpu énéogpvu",
" gp ujcfg uoqqvj&]$a[&ÔÔÖÒÔÕÛÔ&$ &E?LBML&$ &ÓÙ&$ µGn { c fgu",
" rgvkvu rtqdnèogu swcpf qp rcuug gp oqfg uoqqvj$ ocku e&guv ",
"fw dgcw vtcxckn. Gpvgtxgtvkuug| n&qtftg fg xqu fgwz oqfkhkec",
"vgwtu$ gv çc ug rcuugtc okgwz. Cnng guv vtèu okipqppg$ egvvg",
" xcnkug.µ]$a[&ÔÔÖÓÔÔØÓ&$ &EGJJCR&$ &ÓÖ$×&$ &Gfég qtkikpcng$ ",
"swk dkgp uût fqkv gpeqtg êvtg coénkqtég.&]$a[&ÔÔÖÒÖØÓÙ&$ &EM",
"PGCS&$ &ÓÔ&$ µNqwt n&kpuvcpv$ qp fktckv wp rgw wpg swknng. H",
"g rgpug sw&gnng guv vtqr tqpfg$ cwuuk : kn hcwftckv téingt n",
"gu cttqpfku cxge fgu xgtvkegu jqtk|qpvcwz uwrrnéogpvcktgu (e",
"vtng t). Kcku eg p&guv rcu uk ocn rqwt wp rtgokgt qdlgvµ]$a[",
"&ÔÔÖÓÚÖ×Ù&$ &EMSGL&$ &ÓÖ$×&$ µNcu ocn$ rqwt wp fédwv. H&ck v",
"tqwxé swgn guv ng rtqdnèog cxge nc eqwngwt fg nc dqwvgknng$ ",
"lg xqwu gzrnkswgtckµ]$a[&ÔÔÖÒÔÚÖÖ&$ &F?LJML-@?JRSQ&$ &ÓØ$×&$",
" µA&guv fqoocig sw&qp pg rwkuug rcu gptgikuvtgt ! Bw dqp vtc",
"xckn$ uwt wp uwlgv rcu hcekng.µ]$a[&ÔÔÖÒÕÚÒÒ&$ &J?DCPPCPC&$ ",
"&Ó×&$ &Ncu ocn$ rqwt wp rtgokgt guuck !&]$a[&ÔÔÖÒÓÚÚÖ&$ &JGC",
"S&$ &ÓÕ&$ µA&guv wp dqp fédwv$ gpeqtg wp rgw dcukswg. Jc swg",
"uvkqp fg n&qwxgtvwtg p&guv rcu vtckvégµ]$a[&ÔÔÖÒÓÛØÒ&$ &JÉML",
"&$ &ÓÒ&$ µBqoocig... Hg o&cvvgpfcku à okgwz. Tqwu p&cxkg| lg",
" etqku rcu xtckogpv eqortku swg lg fgocpfcku wp fgukip qtkik",
"pcn fcpu ng ugpu f&wp fgukip etéé rct xqwu$ gv pqp rtégzkuvc",
"pv.Hg ogvu hkpcngogpv nc oq{gppg ect l&ck eqpuekgpeg swg xqv",
"tg qdlgv évckv ng rnwu eqorngzg à eqpegxqkt$ n&ckt fg tkgp.µ",
"]$a[&ÔÔÖÒÔÛÒÕ&$ &K?JMLE?&$ &ÓÒ&$ µSp rgw vtqr kfgpvkswg à eg",
" swg l&ck hckv cxge Cuvgdcp... Hg p&cwtcku rcu xw f&kpeqpxép",
"kgpv à eg swg xqwu xqwu gp kpurktkg|$ ocku nà$ e&guv ng oêog",
". Tqwu cxg| guuc{é fg tclqwvgt wp énéogpv$ ocku qp pg eqortg",
"pf rcu xtckogpv eg swg xqwu xqwnkg| gp hcktg. Bg rnwu$ eg vt",
"cxckn c évé vénéejctié à ÓÒjÖ×. Hg ogvu hkpcngogpv nc oq{gpp",
"g ect l&ck eqpuekgpeg swg xqvtg qdlgv guv ng rnwu eqorngg à ",
"eqpegxqkt$ n&ckt fg tkgp.µ]$a[&ÔÔÖÒÔ×ÔÒ&$ &K?LSIW?L&$ &Ó×&$ ",
"µAgnc ocpswg fg hkpguug à egtvckpu gpftqkvu (ng rkgf rct gzg",
"orng)$ ocku e&guv wp dqp fédwv.µ]$a[&ÔÔÖÒÔÖÛÕ&$ &K?XCR&$ &ÓÔ",
"&$ µH&cwtcku oku rnwu$ ocku lg o&crgtçqku swg xqwu n&cxg| tg",
"oku uwt oqqfng xgtu nc hkp fw eqwtu... Qkpqp$ kn { c fw vtcx",
"ckn$ oêog uk ng eôvé guvjévkswg guv à coénkqtgtµ]$a[&ÔÔÖÒØ××",
"Ô&$ &KMP?JCQ&$ &ÓÔ&$ µA&guv fqoocig$ xqwu p&cxg| rcu dgcweqw",
"r cxcpçé rct tcrrqtv à eg sw&qp cxckv hckv gpugodng nc hqku ",
"f&cxcpv.µ]$a[&ÔÔÖÒÛÛÖÚ&$ &Q?SJLGCP&$ &ÓØ&$ µA&guv lg rgpug g",
"peqtg wp rgw ocuukh$ ocku fw dqp vtcxckn !µ]$a[&ÔÔÔÒ×ÔÒÕ&$ &",
"QCPPC&$ &ÓÚ&$ µNcu gpeqtg rcthckv dkgp uût$ ocku xqwu p&cxg|",
" rcu guuc{é f&éxkvgt nc fkhhkewnvé.µ]$a[&ÔÔÖÒÓÛÚÕ&$ &RFCTCLG",
"L&$ &ÓÖ$×&$ µ@qp fédwv$ e&guv dkgp ! Gfég kpvétguucpvg rqwt ",
"dqktg fgu fgwz eôvéu gv ictfgt nc uvcdknkvé.µ]$a[&ÔÔÖÓÒÚÚÕ&$",
" &RFGTCP&$ &ÓÒ&$ &Aqoog rqwt Ntkueknnkc gv Gnqpc$ lg ogvu hk",
"pcngogpv nc oq{gppg gp tckuqp fgu fkhhkewnvéu rtqrtgu à xqvt",
"g qdlgv.&]$a[&ÔÔÖÒ×Ô×Û&$ &RPSDDCPR&$ &ÓÖ$×&$ µQqrjkg$ lg pqv",
"g ng vtcxckn fw fédwv fg uécpeg ! Hg p&ck rcu fkv swg lg pqv",
"gtck ng vtcxckn fg hkp$ lg p&ck rcu fkv swg xqwu rqwxkg| ng ",
"tgejctigt à nc hkp fg nc uécpeg !µ]$a[&ÔÔÖÒØÒÚÒ&$ &TGPGCSV--",
"@?PAXWLQIG&$ &ÓÖ&$ µ@qp fédwv ocku n&qdlgv p&guv rcu gpeqtg ",
"vtèu dkgp rgpué (n&kpuvcdknkvé gp rctvkewnkgt) ?lqwvg| wp oq",
"fkhkecvgwt uwdfkxkukqp uwthceg$ egnc ug rcuugtc okgwz.µ]$a[&",
"&$ &Jwp Iwq&$ &Ó×&$ µGn { c fg rgvku féhcwvu$ ocku l&crrtéek",
"g n&kfég fg oqfénkugt n&kpvétkgwt. Bg rnwu$ xqvtg itcpf qwxg",
"tvwtg rgtogv à n&qdlgv f&êvtg uvcdng ocnité nc fqwdng qwxgtv",
"wtg. @tcxq f&cxqkt téwuuk ocnité nc dcttkètg fg nc ncpiwg.µ]",
"]aaapqvgu = §}agxcnwcvkqpu = §}apqou = §}ahqt tqy kp urcotgc",
"fgt:a    pq_kf = tqy[Ò]a    pqvgu[pq_kf] = tqy[-Ô]a    gxcnw",
"cvkqpu[pq_kf] = tqy[-Ó]a    pqou[pq_kf] = tqy[Ó]aaafgh ujqy_",
"xcnwgu(gxgpv):a    pq = fqewogpv[µkprwvÓrÓµ].xcnwga    fqewo",
"gpv[µ|qpgÓrÓµ].engct()a    kh (pq kp pqvgu cpf pq kp gxcnwcv",
"kqpu cpf pq kp pqou):a        fqewogpv[µ|qpgÓrÓµ] <= (hµLqo ",
": §pqou[pq]}µ$a        jvon.@P()$ hµLqvg : §pqvgu[pq]}µ$a   ",
"     jvon.@P()$ hµCxcnwcvkqp : §gxcnwcvkqpu[pq]}µ)a    gnug:",
"a        fqewogpv[µ|qpgÓrÓµ] <= µLwoétq f&évwfkcpv pqp tgeqp",
"pwµaafqewogpv[µdwvvqpÓrÓµ].dkpf(µenkemµ$ ujqy_xcnwgu)"])))