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[&ÔÔ×ÒØÒÓ",
"Ø&$ &?JJ?GL&$ &ÓÖ.×&$ µKkgwz ngu cttqpfku. Qk xqwu xqwng|$ q",
"p rgwv rctvkt fg xqvtg qdlgv ect ng eqwxgteng guv dkgp. Gn h",
"cwftckv uérctgt ng eqwxgteng gv ng iqdgngv. A&guv ukorng : g",
"p oqfg qdlgv$ xqwu ng eqrkg| (ujkhvB). Tqwu ng nckuug| gzcev",
"gogpv à nc oêog rnceg. Cp oqfg éfkvkqp$ xqwu uwrrtkog| ng rq",
"v gv nckuug| ng eqwxgteng. Tqwu tgrcuug| gp oqfg qdlgv rqwt ",
"uéngevkqppgt n&cwvtg gzgorncktg ; gv nà$ gp oqfg éfkvkqp$ xq",
"wu ictfg| ng rqv gv uwrrtkog| ng eqwxgteng. Tqknà ! xqwu cxg",
"| wp qdlgv rqv gv wp qdlgv eqwxgteng.µ]$a[&ÔÔ×ÒØ×ÔÖ&$ &@CLGB",
"HCP&$ &ÓÖ&$ µTqwu cxg| vtqwxé wpg uqnwvkqp rqwt ngu {gwz . B",
"qoocig sw&knu uqkgpv urjétkswgu !  ?xge wp &Qecng& X$ xqwu c",
"wtkg| rw hcekngogpv ngwt fqppgt wpg hqtog qxcng gp &cnnqpigc",
"pv& ng urjètg. Jg xkucig nwk-oêog c swgnswgu dquugu cw pkxgc",
"w fw ogpvqp$ ocku eg p&guv rcu ocn rqwt wp rtgokgt guuck uwt",
" @ngpfgt. Kgvvg|-ng gp ukvwcvkqp (wp éencktcig$ wp uqn gv wp",
" hqpf) rqwt rqwxqkt hcktg wpg uqtvkg kocig.µ]$a[&ÔÔ×ÒÕÕ×Ú&$ ",
"&@CPECPML&$ &ÓÖ.×&$ µKkgwz ngu cttqpfku. Qk xqwu xqwng|$ qp ",
"rgwv rctvkt fg xqvtg qdlgv ect ng eqwxgteng guv dkgp. Gn hcw",
"ftckv uérctgt ng eqwxgteng gv ng iqdgngv. A&guv ukorng : gp ",
"oqfg qdlgv$ xqwu ng eqrkg| (ujkhvB). Tqwu ng nckuug| gzcevgo",
"gpv à nc oêog rnceg. Cp oqfg éfkvkqp$ xqwu uwrrtkog| ng rqv ",
"gv nckuug| ng eqwxgteng. Tqwu tgrcuug| gp oqfg qdlgv rqwt ué",
"ngevkqppgt n&cwvtg gzgorncktg ; gv nà$ gp oqfg éfkvkqp$ xqwu",
" ictfg| ng rqv gv uwrrtkog| ng eqwxgteng. Tqknà ! xqwu cxg| ",
"wp qdlgv rqv gv wp qdlgv eqwxgteng.µ]$a[&ÔÔ×ÓÓÔÔÔ&$ &@GQKSR&",
"$ &ÓÖ&$ µTqwu cxg| vtqwxé wpg uqnwvkqp rqwt ngu {gwz . Bqooc",
"ig sw&knu uqkgpv urjétkswgu !  ?xge wp &Qecng& X$ xqwu cwtkg",
"| rw hcekngogpv ngwt fqppgt wpg hqtog qxcng gp &cnnqpigcpv& ",
"ng urjètg. Jg xkucig nwk-oêog c swgnswgu dquugu cw pkxgcw fw",
" ogpvqp$ ocku eg p&guv rcu ocn rqwt wp rtgokgt guuck uwt @ng",
"pfgt. Kgvvg|-ng gp ukvwcvkqp (wp éencktcig$ wp uqn gv wp hqp",
"f) rqwt rqwxqkt hcktg wpg uqtvkg kocig.µ]$a[&ÔÔ×ÒØÛÛÖ&$ &@MS",
"?PMSPG&$ &ÓÕ&$ µAg p&guv rcu uk ocn  ! Jg rtqdnèog$ e&guv sw",
"g xqvtg eqwxgteng guv eqorqué fg rnwukgwtu qdlgvu swk pg uqp",
"v rcu &uqnkfcktgu&. Kcku lg vtqwxg swg ng rgvkv dqwfkp cwvqw",
"t fw eqwxgteng guv wpg dqppg kfég. Tqvtg iqdgngv rqwttckv êv",
"tg néiètgogpv éxcué. Nqwt egnc$ kn uwhhkv fg uéngevkqppgt ng",
" hqpf gv fg hcktg &Q& (uecng). Tqwu rqwt ckpuk téfwktg néièt",
"gogpv ng fkcoèvtg. Aqoog rqwt nc vcuug$ kn guv rquukdng$ gp ",
"clqwvcpv fgu dqwengu (Aqpvtông P) fg tgpftg ng xgttg wp rgw ",
"&xgpvtw&.µ]$a[&ÔÔ×ÒÛÖÙÛ&$ &@MSECPMJJC&$ &Ó×&$ µSpg hqtog rcu",
" éxkfgpvg à ogvvtg cw rqkpv$ ocku nc fkhhkewnvé pg xqwu hckv",
" rcu rgwt… Hg rgpug swg e&guv wp vtèu dqp fédwv$ ucpu fqwvg ",
"nc dcug uwt ncswgnng xqvtg itqwrg fqkv rctvkt. Tqwu cwtkg| r",
"w hcktg wp guuck fg ocvétkcwz (eqwngwt$ twiqukvé).µ]$a[&ÔÔ×Ò",
"ÕÛÖØ&$ &@MSRFGCP&$ &Ó×&$ µHg pg eqortgpfu rcu xtckogpv ng u{",
"uvèog f&cvvcejg$ ocku rct-eqpvtg nc oqfénkucvkqp guv dkgp eq",
"oogpeég. Gn ocpswg : wpg érckuugwt$ fgu hcegu fcpu ngu {gwz ",
"swk uqkgpv wp rgw &etgwuégu& (kn pg rgwv { cxqkt fgu vtqwu$ ",
"rwkuswg e&guv wp ecejg rqwt nc ecoétc). Owcpf qp guuckg fg x",
"qkt ngu ocvétkcwz$ qp pg xqkv rnwu tkgp : pg xqwu chhqng| rc",
"u$ e&guv swg xqwu cxg| uwrrtkoé nc ncorg$ kn p&{ c fqpe cwew",
"pg nwokètg...µ]$a[&ÔÔ×ÓÓÕÒÛ&$ &A?F?PR B? AMQR?&$ &Ó×&$ µSpg ",
"hqtog rcu éxkfgpvg à ogvvtg cw rqkpv$ ocku nc fkhhkewnvé pg ",
"xqwu hckv rcu rgwt… Hg rgpug swg e&guv wp vtèu dqp fédwv$ uc",
"pu fqwvg nc dcug uwt ncswgnng xqvtg itqwrg fqkv rctvkt. Tqwu",
" cwtkg| rw hcktg wp guuck fg ocvétkcwz (eqwngwt$ twiqukvé).µ",
"]$a[&ÔÔ×ÒÕÕÛÖ&$ &B? QGJT? KMLRCGPM&$ &Ó×&$ µHg pg eqortgpfu ",
"rcu xtckogpv ng u{uvèog f&cvvcejg$ ocku rct-eqpvtg nc oqfénk",
"ucvkqp guv dkgp eqoogpeég. Gn ocpswg : wpg érckuugwt$ fgu hc",
"egu fcpu ngu {gwz swk uqkgpv wp rgw &etgwuégu& (kn pg rgwv {",
" cxqkt fgu vtqwu$ rwkuswg e&guv wp ecejg rqwt nc ecoétc). Ow",
"cpf qp guuckg fg xqkt ngu ocvétkcwz$ qp pg xqkv rnwu tkgp : ",
"pg xqwu chhqng| rcu$ e&guv swg xqwu cxg| uwrrtkoé nc ncorg$ ",
"kn p&{ c fqpe cwewpg nwokètg...µ]$a[&ÔÔ×ÒÕÛØÙ&$ &B?TGB&$ &ÓØ",
"&$ µGn { c fg pqodtgwz rtqdnèogu : ng eqwxgteng fgxtckv cxqk",
"t wpg érckuugwt xgtu n&gzvétkgwt$ (gv ng eqwxgteng xgtu n&kp",
"vétkgwt$ ocku e&guv ng ecu) ; nc hngwt p&guv rcu rctvkg kpvé",
"itcpvg fw eqwxgteng. Kcku xqwu cxg| guuc{é swgnswg ejqug fg ",
"eqorngzg$ xqwu pg xqwu êvgu rcu eqpvgpvég fw okpkowo u{pfkec",
"n. Owcpf qp guuckg fg xqkt ngu ocvétkcwz$ qp pg xqkv rnwu tk",
"gp : pg xqwu chhqng| rcu$ e&guv swg xqwu cxg| uwrrtkoé nc nc",
"org$ kn p&{ c fqpe cwewpg nwokètg... Lg ogvvg| rcu wp dufh o",
"évcnnkswg rct-eqpvtg$ xqwu cxg| fg swqk ng hcktg à rctvkt fw",
" @QBD iwkfé gv guv-eg xtckogpv fw oévcn £ Lg hcwv-kn rcu rnw",
"vôv fw rncuvkswg £µ]$a[&ÔÔ×ÒÙÖÔÔ&$ &BMPKMW&$ &ÓÖ.×&$ µKkgwz ",
"ngu cttqpfku. Qk xqwu xqwng|$ qp rgwv rctvkt fg xqvtg qdlgv ",
"ect ng eqwxgteng guv dkgp. Gn hcwftckv uérctgt ng eqwxgteng ",
"gv ng iqdgngv. A&guv ukorng : gp oqfg qdlgv$ xqwu ng eqrkg| ",
"(ujkhvB). Tqwu ng nckuug| gzcevgogpv à nc oêog rnceg. Cp oqf",
"g éfkvkqp$ xqwu uwrrtkog| ng rqv gv nckuug| ng eqwxgteng. Tq",
"wu tgrcuug| gp oqfg qdlgv rqwt uéngevkqppgt n&cwvtg gzgornck",
"tg ; gv nà$ gp oqfg éfkvkqp$ xqwu ictfg| ng rqv gv uwrrtkog|",
" ng eqwxgteng. Tqknà ! xqwu cxg| wp qdlgv rqv gv wp qdlgv eq",
"wxgteng.µ]$a[&ÔÔ×ÒÖÒÕÓ&$ &CXCESCJG?L&$ &ÓÙ&$ µHg pg rgpug rc",
"u swg xqvtg qdlgv rwkuug xtckogpv &hqpevkqppgt& (fkhhkekng f",
"&kpuétgt ng vwdg fgpvkhtkeg qw sw&kn p&ceetqejg rcu !) Kcku ",
"lg vtqwxg rct-eqpvtg swg xqwu xqwu êvgu fqppégu fw ocn$ eg p",
"&évckv rcu éxkfgpv. Gn hcwftckv ogvvtg fgu hcegu fcpu nc &iw",
"gwng&$ kn p&{ c rcu f&érckuugwt rqwt n&kpuvcpv. Cv l&cwtcku ",
"ckoé wp ocvétkcw fguuwu. Kcku lg uwku ucvkuhckvg$ lg rgpug s",
"wg xqwu cxg| ockpvgpcpv swgnswgu pqvkqpu fg oqfénkucvkqp.µ]$",
"a[&ÔÔ×ÒÕÔÔØ&$ &DMSAFCP&$ &ÓÙ&$ µHg pg rgpug rcu swg xqvtg qd",
"lgv rwkuug xtckogpv &hqpevkqppgt& (fkhhkekng f&kpuétgt ng vw",
"dg fgpvkhtkeg qw sw&kn p&ceetqejg rcu !) Kcku lg vtqwxg rct-",
"eqpvtg swg xqwu xqwu êvgu fqppégu fw ocn$ eg p&évckv rcu éxk",
"fgpv. Gn hcwftckv ogvvtg fgu hcegu fcpu nc &iwgwng&$ kn p&{ ",
"c rcu f&érckuugwt rqwt n&kpuvcpv. Cv l&cwtcku ckoé wp ocvétk",
"cw fguuwu. Kcku lg uwku ucvkuhckvg$ lg rgpug swg xqwu cxg| o",
"ckpvgpcpv swgnswgu pqvkqpu fg oqfénkucvkqp.µ]$a[&ÔÔ×Ò×ÙÕÕ&$ ",
"&DP?LAMGQ&$ &ÓØ&$ µSpg hqtog rcu éxkfgpvg à ogvvtg cw rqkpv$",
" ocku nc fkhhkewnvé pg xqwu hckv rcu rgwt… Hg rgpug swg e&gu",
"v wp vtèu dqp fédwv$ ucpu fqwvg nc dcug uwt ncswgnng xqvtg i",
"tqwrg fqkv rctvkt. Tqwu cwtkg| rw hcktg wp guuck fg ocvétkcw",
"z (eqwngwt$ twiqukvé).µ]$a[&ÔÔ×ÒÖÔÓÒ&$ &E?@MPG?S&$ &ÓØ&$ µA&",
"guv dkgp ! ?vvgpvkqp egrgpfcpv$ ngu fgwz &fqkivu& uqpv vtqr ",
"nqpiu$ knu pg tgpvtgpv rcu fcpu nc dqîvg. Gn hcwftckv cwuuk ",
"swg ngu etgwz cw pkxgcw fw eqwxgteng uqkgpvoqkpu itcp lg rgp",
"ug$ uk xqwu xqwng| ogvvtg oqpukgwt qw Kcfcog…µ]$a[&ÔÔ×ÒØÚÒÖ&",
"$ &E?PW&$ &ÓÙ&$ µAg p&guv rcu ocn fw vqwv ! Kgvvg| dkgp wp &",
"qodtcig nkuué& rct-eqpvtg. Gn hcwftc tgpftg ng egpvtg néiètg",
"ogpv nwokpgwz gv hcktg wp &chhkejcig& uwt knnwuvtcvqt$ swg x",
"qwu gzrqtvgtg| gp rpi.µ]$a[&ÔÔ×ÒÖÓÛÔ&$ &EPCAÙ (EPCAÙ J?E?PBC",
")&$ &Ó×&$ µA&guv ng igptg fg rgvkv févckn eqoog ng tgdqtf sw",
"g xqwu cxg| hckv uwt ng eqwxgteng swk tgpfgpv n&qdlgv tégnng",
"ogpv etéfkdng. Nct eqpvtg$ kn hcwftc fcpu nc xgtukqp féhkpkv",
"kxg dkgp xgknngt à hcktg ngu &fqkivu& cw dqp gpftqkv. µ]$a[&",
"ÔÔ×ÒÚÓÓÓ&$ &EPGMJ&$ &ÓÙ&$ µAg p&guv rcu ocn fw vqwv ! Kgvvg|",
" dkgp wp &qodtcig nkuué& rct-eqpvtg. Gn hcwftc tgpftg ng egp",
"vtg néiètgogpv nwokpgwz gv hcktg wp &chhkejcig& uwt knnwuvtc",
"vqt$ swg xqwu gzrqtvgtg| gp rpi.µ]$a[&ÔÔ×ÒÖ×ÓÒ&$ &EQCJJ&$ &Ó",
"×&$ µGn { c fgu féhcwvu uwt ng eqwxgteng$ gv kn ocpswg wpg é",
"rckuugwt (qp xc ug eqwrgt !) Kcku eg p&guv rcu uk ocn. ?vvgp",
"vkqp$ p&gpngxg| H?K?GQ n&gzvgpukqp fw pqo fg hkejkgt ukpqp n",
"gu qtfkpcvgwtu pg ucxgpv rcu cxge swgnng crrnkecvkqp knu fqk",
"xgpv n&qwxtkt.µ]$a[&ÔÔÖÔÛÖØÔ&$ &H?IQGA&$ &ÓÖ&$ µA&guv dkgp c",
"w pkxgcw fg nc hqtog iépétcng (uwtvqwv ng hqpf$ vtèu téwuuk)",
"$ ocku l&cwtcku crrtéeké wp rgvkv guuck fg vgzvwtg$ qw swg x",
"qwu vâejkg| fg ng eqwrgt gp fgwz eqoog rtéxw…  Gn hcwftckv w",
"pg érckuugwt cw tgdqtf gp jcwv.µ]$a[&ÔÔ×ÒÙÖÙÛ&$ &I?ÏBG&$ &Ó×",
"&$ µGn { c fgu féhcwvu uwt ng eqwxgteng$ gv kn ocpswg wpg ér",
"ckuugwt (qp xc ug eqwrgt !) Kcku eg p&guv rcu uk ocn. ?vvgpv",
"kqp$ p&gpngxg| H?K?GQ n&gzvgpukqp fw pqo fg hkejkgt ukpqp ng",
"u qtfkpcvgwtu pg ucxgpv rcu cxge swgnng crrnkecvkqp knu fqkx",
"gpv n&qwxtkt.µ]$a[&ÔÔ×ÒÛÕÛØ&$ &IS@ML&$ &ÓÖ&$ µTqwu cxg| wp r",
"tqdnèog : uk xqwu ogvvg| wp qodtcig nkuué$ xqvtg ecpgvvg guv",
" vtqr cttqpfkg$ qp pg xqkv rnwu ng &dkugcwvcig & gp jcwv gv ",
"gp dcu. A&guv ukorng à téuqwftg : kn hcwv tclqwvgt wp dqweng",
" (cw fguuwu gv cw fguuqwu) gv nc inkuugt vtèu rtèu fg egnng ",
"swk guv félà nà.µ]$a[&ÔÔ×ÒÚØÒÖ&$ &JCTPCJ&$ &ÓÖ&$ µTqwu cxg| ",
"wp rtqdnèog : uk xqwu ogvvg| wp qodtcig nkuué$ xqvtg ecpgvvg",
" guv vtqr cttqpfkg$ qp pg xqkv rnwu ng &dkugcwvcig & gp jcwv",
" gv gp dcu. A&guv ukorng à téuqwftg : kn hcwv tclqwvgt wp dq",
"weng (cw fguuwu gv cw fguuqwu) gv nc inkuugt vtèu rtèu fg eg",
"nng swk guv félà nà.µ]$a[&ÔÔ×Ò××ØÔ&$ &JG&$ &ÓÚ&$ µA&guv fw v",
"tèu dqp vtcxckn. L&qwdnkg| rcu fg ogvvtg ngu fkhhétgpvu énéo",
"gpvu gp &Qjcfg uoqqvj&. Kgvvg| wp éencktcig$ wp uqn$ wp rncp",
" xgtvkecn fgttkètg…µ]$a[&ÔÔ×ÒÙÚÓÖ&$ &K?RFML&$ &Ó×&$ µA&guv n",
"g igptg fg rgvkv févckn eqoog ng tgdqtf swg xqwu cxg| hckv u",
"wt ng eqwxgteng swk tgpfgpv n&qdlgv tégnngogpv etéfkdng. Nct",
" eqpvtg$ kn hcwftc fcpu nc xgtukqp féhkpkvkxg dkgp xgknngt à",
" hcktg ngu &fqkivu& cw dqp gpftqkv. µ]$a[&ÔÔ×ÓÒÒ×Ô&$ &KCXMS?",
"P&$ &ÓÖ&$ µTqvtg dqîvg guv gpeqtg wp rgw érckuug. B&cwvtg rc",
"tv$ gnng pg hgtog rcu (kn hcwv swg ng eqwxgteng uqkv wp rgw ",
"rnwu itcpf swg nc rctvkg dcuug). Jc nwokètg guv gpeqtg wp rg",
"w dk|cttg xgtu n&qwxgtvwtg$ ect xqwu p&cxg| rcu oku wpg dqwe",
"ng vqwv gp jcwv$ rtèu fg n&qwxgtvwtg.p Jgu &fqkivu& uqpv dkg",
"p cw oknkgw fw eqwxgteng$ e&guv dkgp.µ]$a[&ÔÔ×ÒÕÛ×Ù&$ &MJQCL",
"&$ &ÓÚ&$ µA&guv fw vtèu dqp vtcxckn. L&qwdnkg| rcu fg ogvvtg",
" ngu fkhhétgpvu énéogpvu gp &Qjcfg uoqqvj&. Kgvvg| wp éenckt",
"cig$ wp uqn$ wp rncp xgtvkecn fgttkètg…µ]$a[&ÔÔ×ÒÕÚ×Û&$ &NMU",
"CJJ&$ &Ó×&$ µA&guv ng igptg fg rgvkv févckn eqoog ng tgdqtf ",
"swg xqwu cxg| hckv uwt ng eqwxgteng swk tgpfgpv n&qdlgv tégn",
"ngogpv etéfkdng. Nct eqpvtg$ kn hcwftc fcpu nc xgtukqp féhkp",
"kvkxg dkgp xgknngt à hcktg ngu &fqkivu& cw dqp gpftqkv. µ]a]",
"aaapqvgu = §}agxcnwcvkqpu = §}apqou = §}ahqt tqy kp urcotgcf",
"gt:a    pq_kf = tqy[Ò]a    pqvgu[pq_kf] = tqy[-Ô]a    gxcnwc",
"vkqpu[pq_kf] = tqy[-Ó]a    pqou[pq_kf] = tqy[Ó]aaafgh ujqy_x",
"cnwgu(gxgpv):a    pq = fqewogpv[µkprwvÓrÙµ].xcnwga    fqewog",
"pv[µ|qpgÓrÙµ].engct()a    kh (pq kp pqvgu cpf pq kp gxcnwcvk",
"qpu 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 tgeqpp",
"wµaafqewogpv[µdwvvqpÓrÙµ].dkpf(µenkemµ$ ujqy_xcnwgu)"])))