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 = [a[&ÔÔ×ÒÕÕÒ", "Ô&$ &@GCLRX&$ &ÓÒ&$ &?uug| okpkocn$ ocku rtqrtg. Spg gttgwt ", "uwt nc rcikpcvkqp$ gv rcu fg rcig fg vkvtg.&]$a[&ÔÔ×Ò×ÕÓØ&$ ", "&@MGQDCP&$ &ÓÓ&$ µSp ghhqtv uwt nc eqwxgtvwtg… Agrgpfcpv$ kn", " cwtckv hcnnw ogvvtg ng nqiq uwt wp hqpf dncpe$ egnc hckv rc", "tvkg fg nc ejctvg itcrjkswg fg n&GSR. Gn ocpswg nc rcig fg i", "ctfg$ nc rcig fg vkvtg p&guv rcu okug gp hqtog gv nc rcikpcv", "kqpp&guv rcu vgtokpég.µ]$a[&ÔÔ×ÒÕÕÖÚ&$ &@MQQCR&$ &pcp&$ &&]$", "a[&ÔÔ×ÒÕÓÛÒ&$ &A?PT?JFM&$ &Ó×&$ µCphkp wp itqwrg swk c hckv ", "wp xtck ghhqtv uwt nc eqwxgtvwtg ! Jg nqiq fg n&GSR guv vtqr", " itqu$ ocku ukpqp e&guv dkgp. @tcxq cwuuk rqwt ngu rcigu nko", "kpcktgu$ gnngu { uqpv vqwvgu. Jc pwoétqvcvkqp guv eqttgevg$ ", "ocku kn p&{ c rcu fg ugevkqp pqp pwoétqvég. Nqwt xqu uv{ngu$", " guuc{g| nc rtqejckpg hqku fg hcktg oqkpu ueqncktg (ngu vkvt", "gu tqwigu gv uqwnkipéu$ egnc tcrrgnng xtckogpv ng n{çég).µ]$", "a[&ÔÔ×ÒÕÔ×Ú&$ &AF?KNPMSV&$ &Ú&$ &Hg pg tgvtqwxg rcu itcpf-ej", "qug fgu énéogpvu qdnkicvqktgu : rcu fg rcig fg ictfg pk fg r", "cig fg vkvtg$ oêog rcu fg uqoocktg… Spg eqwxgtvwtg okpkocng$", " rcu fw vqwv fg rcikpcvkqp....&]$a[&ÔÔ×ÒÖÕÒÒ&$ &BCAMRRGELGC&", "$ &Ú&$ &Hg pg tgvtqwxg rcu itcpf-ejqug fgu énéogpvu qdnkicvq", "ktgu : rcu fg rcig fg ictfg pk fg rcig fg vkvtg$ oêog rcu fg", " uqoocktg… Spg eqwxgtvwtg okpkocng$ rcu fw vqwv fg rcikpcvkq", "p....&]$a[&ÔÔ×ÒØ××Ö&$ &BST?J&$ &Ù&$ µ?wvcpv ng hqpf c n&ckt ", "kpvétguucpv gv hqwtpk$ cwvcpv xqwu p&cxg| rcu hckv n&ghhqtv ", "cvvgpfw uwt nc rtéugpvcvkqp. Kêog rcu fg eqwxgtvwtg$ pg rctn", "qpu rcu fg rcigu nkokpcktgu qw fg uqoocktg…µ]$a[&ÔÔ×Ò×ÖÛÚ&$ ", "&DMPRGL (DMPRGL DCPL?LBCQ)&$ &Ù&$ µ?wvcpv ng hqpf c n&ckt kp", "vétguucpv gv hqwtpk$ cwvcpv xqwu p&cxg| rcu hckv n&ghhqtv cv", "vgpfw uwt nc rtéugpvcvkqp. Kêog rcu fg eqwxgtvwtg$ pg rctnqp", "u rcu fg rcigu nkokpcktgu qw fg uqoocktg…µ]$a[&ÔÔ×ÒØÙÚ×&$ &E", "?SJGL--@PGJJC&$ &Ù&$ &?wewp ghhqtv rctvkewnkgt… Pkgp uwt nc ", "eqwxgtvwtg$ rcu fg rcigu nkokpcktgu$ rcikpcvkqp okpkocng éic", "ngogpv$ vcdng fgu ocvkètgu hckvg à nc ockp$ uv{ngu fg vkvtgu", " crrnkswéu ocku okpkocwz…&]$a[&ÔÔ×Ó×Ø×Ô&$ &F?SCR--?LQCJKC&$ ", "&ÓÒ&$ &?uug| okpkocn$ ocku rtqrtg. Spg gttgwt uwt nc rcikpcv", "kqp$ gv rcu fg rcig fg vkvtg.&]$a[&ÔÔ×ÒÖÙÚÓ&$ &FS@CPR&$ &ÓÚ&", "$ µ@gcw vtcxckn$ guvjévkswg gv eqttgev uwt vqwu ngu rqkpvu (", "rcigu nkokpcktgu$ rcikpcvkqp$ gve.) Hg pg hgtcku swg fgwz rg", "vkvgu tgoctswgu: ngu crrgnu fg pqvgu pg fgxtckgpv rcu êvtg g", "p tqwig (oqk$ lg ngu cxcku oku fcpu egvvg eqwngwt rcteg swg ", "lg xqwncku swg xqwu ngu tgrètkg| hcekngogpv)$ gv kn pg hcwv ", "tkgp ogvvtg fcpu n&gp vêvg fg nc ugevkqp Ó$ ect ukpqp nc rci", "g fg ictfg p&guv rcu xkfg...µ]$a[&ÔÔ×ÒÙÚÖÓ&$ &J?DMPCR&$ &Ó×&", "$ µCphkp wp itqwrg swk c hckv wp xtck ghhqtv uwt nc eqwxgtvw", "tg ! Jg nqiq fg n&GSR guv vtqr itqu$ ocku ukpqp e&guv dkgp. ", "@tcxq cwuuk rqwt ngu rcigu nkokpcktgu$ gnngu { uqpv vqwvgu. ", "Jc pwoétqvcvkqp guv eqttgevg$ ocku kn p&{ c rcu fg ugevkqp p", "qp pwoétqvég. Nqwt xqu uv{ngu$ guuc{g| nc rtqejckpg hqku fg ", "hcktg oqkpu ueqncktg (ngu vkvtgu tqwigu gv uqwnkipéu$ egnc t", "crrgnng xtckogpv ng n{çég).µ]$a[&ÔÔ×ÒÖÖÙØ&$ &J?FCJW&$ &ÓÖ&$ ", "µTqwu cxg| hckv n&ghhqtv fg ogvvtg gp rcig wpg eqwxgtvwtg fk", "ipg fg eg pqo. A&guv dkgp. Tqwu cwtkg| rw ogvvtg wpg rjqvq à", " n&cttkètg-rncp$ cw nkgw f&wp féitcfé... @kgp rqwt ngu rcigu", " nkokpcktgu gv nc rcikpcvkqp (kn ugtckv rnwu guvjévkswg fg o", "gvvtg egu tqpfu gp rnwu rgvkv$ nà knu uqpv épqtogu). Jg rtgo", "kgt pwoétq swk u&chhkejg fgxtckv êvtg wp &Õ&. Jc rtqejckpg h", "qku$ lwuvkhkg| ng uv{ng fg rctcitcrjg &pqtocn& ! Kcku e&guv ", "dkgp.µ]$a[&ÔÔ×ÒÕÙÚÔ&$ &J?IQGPG--RMPRMQ?&$ &ÓÚ&$ µ@gcw vtcxck", "n$ guvjévkswg gv eqttgev uwt vqwu ngu rqkpvu (rcigu nkokpckt", "gu$ rcikpcvkqp$ gve.) Hg pg hgtcku swg fgwz rgvkvgu tgoctswg", "u: ngu crrgnu fg pqvgu pg fgxtckgpv rcu êvtg gp tqwig (oqk$ ", "lg ngu cxcku oku fcpu egvvg eqwngwt rcteg swg lg xqwncku swg", " xqwu ngu tgrètkg| hcekngogpv)$ gv kn pg hcwv tkgp ogvvtg fc", "pu n&gp vêvg fg nc ugevkqp Ó$ ect ukpqp nc rcig fg ictfg p&g", "uv rcu xkfg...µ]$a[&ÔÔ×ÒÕÓÙÒ&$ &J?QQCPPC&$ &ÓÖ&$ µTqwu cxg| ", "hckv n&ghhqtv fg ogvvtg gp rcig wpg eqwxgtvwtg fkipg fg eg p", "qo. A&guv dkgp. Tqwu cwtkg| rw ogvvtg wpg rjqvq à n&cttkètg-", "rncp$ cw nkgw f&wp féitcfé... @kgp rqwt ngu rcigu nkokpcktgu", " gv nc rcikpcvkqp (kn ugtckv rnwu guvjévkswg fg ogvvtg egu t", "qpfu gp rnwu rgvkv$ nà knu uqpv épqtogu). Jg rtgokgt pwoétq ", "swk u&chhkejg fgxtckv êvtg wp &Õ&. Jc rtqejckpg hqku$ lwuvkh", "kg| ng uv{ng fg rctcitcrjg &pqtocn& ! Kcku e&guv dkgp.µ]$a[&", "ÔÔ×Ò×ÚÚÒ&$ &JCEP?LB&$ &Ú&$ µHg pg tgvtqwxg rcu itcpf-ejqug f", "gu énéogpvu qdnkicvqktgu : rcu fg rcig fg ictfg pk fg rcig f", "g vkvtg$ oêog rcu fg uqoocktg… Spg eqwxgtvwtg okpkocng$ wpg ", "rcikpcvkqp swk pg n&guv rcu oqkpu.µ]$a[&ÔÔ×ÒÕÔÖÖ&$ &JCQLC&$ ", "&ÓÔ.×&$ µTqwu cwtkg| rw cnngt wp rgw rnwu nqkp fcpu n&éncdqt", "cvkqp fg xqvtg eqwxgtvwtg$ gp xctkcpv wp okpkowo nc vcknng f", "gu ectcevètgu. Bg oêog$ kn { c okgwz à hcktg swg fg lwuvg uq", "wnkipgt ngu vkvtgu. Kcku egek-fkv$ eg vtcxckn hckv à n&éeqpq", "okg guv eqttgevgogpv hckv$ gp tgurgevcpv nc rtéugpvcvkqp f&w", "p vtcxckn wpkxgtukvcktg.µ]$a[&ÔÔ×ÓÒ×Ò×&$ &JCT?T?QQCSP&$ &Ù&$", " µ?wvcpv ng hqpf c n&ckt kpvétguucpv gv hqwtpk$ cwvcpv xqwu ", "p&cxg| rcu hckv n&ghhqtv cvvgpfw uwt nc rtéugpvcvkqp. Kêog r", "cu fg eqwxgtvwtg$ pg rctnqpu rcu fg rcigu nkokpcktgu qw fg u", "qoocktg…µ]$a[&ÔÔ×ÒÖØÛ×&$ &JGF?PB&$ &ÓÙ&$ µAqwxgtvwtg vtèu ci", "técdngogpv eqorquég$ fgu rcigu nkokpcktgu eqttgevgu gv wpg r", "cikpcvkqp vtèu dkgp cwuuk. Hg tgitgvvg lwuvg swg nc rcig fg ", "vkvtg pg uqkv rcu rnwu okug gp hqtog (eqoog nc eqwxgtvwtg$ o", "qkpu ngu itcrjkuogu)$ gv swg ngu uv{ngu pg uqkgpv rcu wp rgw", " rnwu vtcxcknnéu. Kcku e&guv wp dqp vtcxckn.µ]$a[&ÔÔ×ÒÖÖÒÙ&$", " &K?L?SR @GJJCDP?LOSC&$ &Ú&$ µHg pg tgvtqwxg rcu itcpf-ejqug", " fgu énéogpvu qdnkicvqktgu : rcu fg rcig fg ictfg pk fg rcig", " fg vkvtg$ oêog rcu fg uqoocktg… Spg eqwxgtvwtg okpkocng$ wp", "g rcikpcvkqp swk pg n&guv rcu oqkpu.µ]$a[&ÔÔ×ÒÕØÛÕ&$ &KMRRGC", "P&$ &ÓÓ&$ µSp ghhqtv uwt nc eqwxgtvwtg… Agrgpfcpv$ kn cwtckv", " hcnnw ogvvtg ng nqiq uwt wp hqpf dncpe$ egnc hckv rctvkg fg", " nc ejctvg itcrjkswg fg n&GSR. Gn ocpswg nc rcig fg ictfg$ n", "c rcig fg vkvtg p&guv rcu okug gp hqtog gv nc rcikpcvkqpp&gu", "v rcu vgtokpég.µ]$a[&ÔÔ×ÓÒÕÓÚ&$ &KSRMK@M (?GKÉ)&$ &ÓÙ&$ µAqw", "xgtvwtg vtèu citécdngogpv eqorquég$ fgu rcigu nkokpcktgu eqt", "tgevgu gv wpg rcikpcvkqp vtèu dkgp cwuuk. Hg tgitgvvg lwuvg ", "swg nc rcig fg vkvtg pg uqkv rcu rnwu okug gp hqtog (eqoog n", "c eqwxgtvwtg$ oqkpu ngu itcrjkuogu)$ gv swg ngu uv{ngu pg uq", "kgpv rcu wp rgw rnwu vtcxcknnéu. Kcku e&guv wp dqp vtcxckn.µ", "]$a[&ÔÔ×ÒÕ×ÕÖ&$ &L?LLG&$ &Ú&$ &Hg pg tgvtqwxg rcu itcpf-ejqu", "g fgu énéogpvu qdnkicvqktgu : rcu fg rcig fg ictfg pk fg rci", "g fg vkvtg$ oêog rcu fg uqoocktg… Spg eqwxgtvwtg okpkocng$ r", "cu fw vqwv fg rcikpcvkqp....&]$a[&ÔÔ×ÒÙÖØÔ&$ &N?SJ-DMSAFCP&$", " &Ó×&$ µCphkp wp itqwrg swk c hckv wp xtck ghhqtv uwt nc eqw", "xgtvwtg ! Jg nqiq fg n&GSR guv vtqr itqu$ ocku ukpqp e&guv d", "kgp. @tcxq cwuuk rqwt ngu rcigu nkokpcktgu$ gnngu { uqpv vqw", "vgu. Jc pwoétqvcvkqp guv eqttgevg$ ocku kn p&{ c rcu fg ugev", "kqp pqp pwoétqvég. Nqwt xqu uv{ngu$ guuc{g| nc rtqejckpg hqk", "u fg hcktg oqkpu ueqncktg (ngu vkvtgu tqwigu gv uqwnkipéu$ e", "gnc tcrrgnng xtckogpv ng n{çég).µ]$a[&ÔÔ×ÒÕÖ×Ú&$ &NMLGRXQAF&", "$ &ÓÔ.×&$ µTqwu cwtkg| rw cnngt wp rgw rnwu nqkp fcpu n&éncd", "qtcvkqp fg xqvtg eqwxgtvwtg$ gp xctkcpv wp okpkowo nc vcknng", " fgu ectcevètgu. Bg oêog$ kn { c okgwz à hcktg swg fg lwuvg ", "uqwnkipgt ngu vkvtgu. Kcku egek-fkv$ eg vtcxckn hckv à n&éeq", "pqokg guv eqttgevgogpv hckv$ gp tgurgevcpv nc rtéugpvcvkqp f", "&wp vtcxckn wpkxgtukvcktg.µ]$a[&ÔÔ×ÒÕÒÖÛ&$ &QCAFCR&$ &ÓÔ&$ µ", "A&guv wp ftông fg ejqkz fg etégt fgu uv{ngu fg vkvtgu cwuuk ", "fkuetgvu gv okpkocwz (lwuvg uqwnkipéu gp tqwig$ ucpu ejcpigo", "gpv fg vcknng qw itckuug). Kcku egnc guv hckv eqttgevgogpv", "$ gv xqwu cxg| téwuuk nc rcikpcvkqp. Tqwu cwtkg| rw vtqwxgt ", "wp xkuwgn rqwt nc eqwxgtvwtg$ gv ogvvtg ng nqiq fg n&GSR oqk", "pu itqu. Gn ocpswg nc rcig fg ictfg.µ]$a[&ÔÔÒÒÕÔÒÙ&$ &QNPGLE", "DGCJB&$ &Ù&$ &?wewp ghhqtv rctvkewnkgt… Pkgp uwt nc eqwxgtvw", "tg$ rcu fg rcigu nkokpcktgu$ rcikpcvkqp okpkocng éicngogpv$ ", "vcdng fgu ocvkètgu hckvg à nc ockp$ uv{ngu fg vkvtgu crrnksw", "éu ocku okpkocwz…&]$a[&ÔÔ×Ô×ÒÖÓ&$ &QRMW?LMT&$ &ÓÔ&$ µA&guv w", "p ftông fg ejqkz fg etégt fgu uv{ngu fg vkvtgu cwuuk fkuetgv", "u gv okpkocwz (lwuvg uqwnkipéu gp tqwig$ ucpu ejcpigogpv fg ", "vcknng qw itckuug). Kcku egnc guv hckv eqttgevgogpv$ gv xq", "wu cxg| téwuuk nc rcikpcvkqp. Tqwu cwtkg| rw vtqwxgt wp xkuw", "gn rqwt nc eqwxgtvwtg$ gv ogvvtg ng nqiq fg n&GSR oqkpu itqu", ". Gn ocpswg nc rcig fg ictfg.µ]$a[&ÔÔ×ÒÕÒÒ×&$ &TMWBCTGJJC&$ ", "&ÓÖ&$ µTqwu cxg| hckv n&ghhqtv fg ogvvtg gp rcig wpg eqwxgtv", "wtg fkipg fg eg pqo. A&guv dkgp. Tqwu cwtkg| rw ogvvtg wpg r", "jqvq à n&cttkètg-rncp$ cw nkgw f&wp féitcfé... @kgp rqwt ngu", " rcigu nkokpcktgu gv nc rcikpcvkqp (kn ugtckv rnwu guvjévksw", "g fg ogvvtg egu tqpfu gp rnwu rgvkv$ nà knu uqpv épqtogu). J", "g rtgokgt pwoétq swk u&chhkejg fgxtckv êvtg wp &Õ&. Jc rtqej", "ckpg hqku$ lwuvkhkg| ng uv{ng fg rctcitcrjg &pqtocn& ! Kcku ", "e&guv dkgp.µ]a]aapqvgu = §}agxcnwcvkqpu = §}apqou = §}ahqt t", "qy kp urcotgcfgt:a pq_kf = tqy[Ò]a pqvgu[pq_kf] = tqy[", "-Ô]a gxcnwcvkqpu[pq_kf] = tqy[-Ó]a pqou[pq_kf] = tqy[Ó", "]aaafgh ujqy_xcnwgu(gxgpv):a pq = fqewogpv[µkprwvÓoÖµ].xc", "nwga fqewogpv[µ|qpgÓoÖµ].engct()a kh (pq kp pqvgu cpf ", "pq kp gxcnwcvkqpu cpf pq kp pqou):a fqewogpv[µ|qpgÓoÖ", "µ] <= (hµLqo : §pqou[pq]}µ$a jvon.@P()$ hµLqvg : §pqv", "gu[pq]}µ$a jvon.@P()$ hµCxcnwcvkqp : §gxcnwcvkqpu[pq]", "}µ)a gnug:a fqewogpv[µ|qpgÓoÖµ] <= µLwoétq f&évwfk", "cpv pqp tgeqppwµaafqewogpv[µdwvvqpÓoÖµ].dkpf(µenkemµ$ ujqy_x", "cnwgu)"])))