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[&ÔÔ×Ò×ÖÖ", "×&$ &?JG @CLW?FG?&$ &Ù&$ µHg xqwncku wp xkuwgn$ gp eqwxgtvwt", "g… Jgu rcigu nkokpcktgu p&{ uqpv rcu. Tqwu cxg| hckv fgwz ug", "evkqpu (xqwu cxg| fgwz rcigu &Ó&)$ dkgp swg nc rcikpcvkqp pg", " uqkv rcu ogpég lwusw&cw dqwv. Tqwu p&cxg| rcu eqortku ngu u", "v{ngu rwkuswg xqwu cxg| crrnkswé wp uv{ng &ceegpvwcvkqp& uwt", " egtvckpu vkvtgu. Aqoog eg p&guv rcu wp uv{ng &vkvtg&$ knu p", "g uqpv rcu rtku gp eqorvg fcpu ng uqoocktg.µ]$a[&ÔÔ×ÒÖÓÖÔ&$ ", "&?LBPCMJCRRG&$ &ÓØ.×&$ µSp ugpu guvjévkswg egtvckp$ vqwv gp ", "uqdtkévé. Agv curgev guv téwuuk. Tqwu cxg| cwuuk kpvéité ngu", " pqvgu. Gn tguvg fgu gttgwtu uwt nc rcikpcvkqp (nc rtgokètg ", "rcig fw uqoocktg fgxtckv êvtg pwoétqvég Õ)$ gv wpg rcig xkfg", " gp vtqr cxcpv ng uqoocktg. Gn pg hcwv rcu sw&crrctckuugxqvt", "g pqo gv xqvtg encuug uwt vqwvgu ngu rcigu$ oêog uk e&guv rq", "uukdng fg ng hcktg à rctvkt fw uqoocktg... Jg rtkpekrg guv g", "zcevgogpv ng oêog swg rqwt nc rcikpcvkqp. Kcku e&guv dkgp f&", "cxqkt xqwnw hcktg rnwu swg ng okpkowo.µ]$a[&ÔÔ×ÒÛÓÒÔ&$ &?QPG", "&$ &ÓÕ.×&$ µAqwxgtvwtg rnwvôv dkgp téwuukg. Jc rcikpcvkqp pg", " eqoogpeg rcu cw dqp gpftqkv$ ocku eqortkug fcpu n&gpugodng.", " QTN$ p&éetkxg| rcu &rcig fg ictfg & !µ]$a[&ÔÔ×ÒÕÓÓ×&$ &?RR?", "J&$ &Ó×&$ µ@qp vtcxckn uwt nc eqwxgtvwtg gv ngu rcigu nkokpc", "ktgu (swcpf oêog : kn hcwv gpngxgt nc ogpvkqp &uqwu-vkvtg& !", "). Cuvjévkswg f&gpugodng ucvkuhckucpvg. Bqoocig$ nc rcikpcvk", "qp.µ]$a[&ÔÔ×ÒÖÒÕØ&$ &?SRGCP&$ &ÓÓ.×&$ µBg dqppgu ejqugu gv f", "&cwvtgu oqkpu ocîvtkuégu. Gn ocpswg nc rcig fg vkvtg$ ng vgz", "vg p&guv rcu lwuvkhké$ nc pwoétqvcvkqp p&guv rcu ugrctég xtc", "kogpv gp fgwz ugevkqpu. Kcku wpg dgnng eqwxgtvwtg$ cxge wp d", "gcw xkuwgn.µ]$a[&ÔÔ×ÒÖÕÛÓ&$ &@?PMAFC--K?ESCR&$ &ÓÛ&$ &Rtèu d", "qp vtcxckn ! Rtèu dgcw gv uqkipé. Gn hcwv lwuvg egpvtgt ng v", "gzvg uwt nc rcig fg vkvtg$ gv kn ocpswg ngu pqvgu fg dcu fg ", "rcig. @tcxq !&]$a[&ÔÔ×Ò×ÔÙØ&$ &@CL RF?@CR - ?XCK WG&$ &ÓØ.×&", "$ µBqoocig$ xqwu rgtfg| fgwz rqkpvu uwt ng pqo fg hkejkgt gv", " ng hqtocv ! A&guv wp dqp vtcxckn cxge fg dqppgu kpkvkcvkxgu", " (ngu gpecftéu). QTN$ pqp$ pg nckuug| rcu nc ogpvkqp rcig fg", " vkvtg uwt nc rcig fg vkvtg$ e&guv éxkfgpv ! @gcw uqoocktg. ", "Kgvvg| ng nqiq gp rgvkv gp dcu fcpu nc rcig fg vkvtg.µ]$a[&Ô", "Ô×ÒÕÖÒÚ&$ &@ÉL?PB&$ &Ù&$ µJc eqwxgtvwtg p&guv rcu kpfkipg$ o", "cku ng tguvg guv hckv c okpkoc$ gv oêog rcu. Jgu rcigu nkokp", "cktgu uqpv pwoétqvégu$ ngu ogpvkqpu eqoog &uqwu-vkvtg& pg uq", "pv rcu gpngxégu$ ngu uv{ngu pg uqpv rcu rgtuqppcnkuéu. &Kkug", " gp htqog& ££ Kcnwu pqo gv hqtocv fg hkejkgt.µ]$a[&ÔÔ×ÒÚ×ÒÙ&", "$ &@CSPPGCP&$ &ÓÒ&$ µL&crrnkswg| rcu ng uv{ng Rkvtg rqwt nc ", "eqwxgtvwtg$ xqwu ugtg| rnwu nkdtg. Rtcxckn lwuvg eqttgev$ c", "xge fgu gttgwtu uwt nc pwoétqvcvkqp gv ngu rcigu nkokpcktgu ", "(rcig dncpejg gp vtqr). Lqo fg hkejkgt : -Ó rqkpv.µ]$a[&ÔÔ×Ò", "ÕÕÔÛ&$ &@J?LAM @CPRP?LB&$ &ÓÕ.×&$ µ@gnng eqwxgtvwtg$ ocku sw", "cpf oêog$ ng nqiq guv ÉLMPKC. H&cxcku rtéekué fg ng ogvvtg r", "gvkv. Tqvtg rcig fg ictfg fqkv swcpf oêog êvtg okug gp hqtog", " fg hcçqp okpkocng (egpvtég$ gv wpg jkétctejkg rgpuég fgu vg", "zvgu$ gv wpg eqorqukvkqp fcpu nc rcig). Tqwu cxg| qoku f&gpn", "gxgt nc pwoétqvcvkqp fcpu nc ugevkqp Ó (ocku félà$ egu ugevk", "qpu gzkuvgpv !).µ]$a[&ÔÔ×ÓÚÓ×Ô&$ &@MSBPC&$ &Û&$ &Tqvtg eqwxg", "tvwtg guv vtqr dcukswg gv kpeqornèvg. Ncig fg vkvtg £ Gn { c", " dkgp fgwz ugevkqpu$ ocku rcu vqwv à hckv cw dqp gpftqkv$ gv", " nc pwoétqvcvkqp fgxtckv eqoogpegt à Õ uwt ng uqoocktg.&]$a[", "&ÔÔ×Ò×ÔÒ×&$ &@MSIMSL?&$ &ÓØ&$ µ@qp vtcxckn$ ocku uxr$ kn guv", " éxkfgpv sw&kn pg hcwv rcu éetktg ng pqo fgu rcigu uwt ngu r", "cigu nkokpcktgu ! Lg ogvvg| rcu ng nqiq fg n&GSR uk itqu pqp", " rnwu.µ]$a[&ÔÔ×ÓÒÛÚÛ&$ &@P?Q DCPPCGP?&$ &ÓÓ&$ µRtcxckn oq{gp", "$ ucpu rnwu : fgu gttgwtu cw pkxgcw fgu rcigu nkokpcktgu (nc", " ogpvkqp &rcig fg vkvtg& gp itqu : pqp dkgp uût ! A&guv lwuv", "g eqoog çc swg nc rcig u&crrgnng ! Gn hcwv gpngxgt egvvg ogp", "vkqp). Jc eqwxgtvwtg p&guv rcu vtèu tgejgtejég. Ngvkvg gttgw", "t cwuuk uwt nc pwoétqvcvkqp fgu rcigu$ ocku rtguswg rcthckv ", "à eg pkxgcw nà. µ]$a[&ÔÔ×ÒÕÚØÛ&$ &@SACJCR&$ &ÓÛ&$ &Rtèu dkgp", "$ dtcxq !&]$a[&ÔÔ×ÒÕÚÒÕ&$ &A?GJJGCPC&$ &ÓÙ&$ µA&guv fw dqp v", "tcxckn ! Lg nckuug| ru nc ogpvkqp &uqwu-vkvtg& uwt nc rcig f", "g vkvtg. Jg nqiq guv wp rgw itqu uwt nc eqwxgtvwtg. @kgp$ nc", " rcikpcvkqp gv ngu uv{ngu.µ]$a[&ÔÔ×ÒÕ×ÓÔ&$ &A?PP?M&$ &ÓÒ&$ µ", "Mp ugpv sw&kn { c fw vtcxckn$ ocku swg eg p&guv rcu gpeqtg o", "cîvtkué. Tqvtg eqwxgtvwtg p&guv rcu ocn$ ; kn { c dgcweqwr f", ">tgwtu uwt ng tguvg (rcigu nkokpcktgu$ pwoétqvcvkqp…) A&gu", "v dkgp$ xqwu cxg| oku ngu pqvgu fg dcu fg rcig$ ocku kn hcwv", " gpngxgt ng pwoétq swg l&ck oku ! Agpvtg| ng vgzvg fg nc rci", "g fg vkvtg. kn xcwv okgwz éxkvgt ngu gpecftéu uwt vqwvgu ngu", " rcigu.µ]$a[&ÔÔ×ÒÖÒÔÙ&$ &A?PPGÉ--K?QCEMQ?&$ &×.×&$ µTqvtg eq", "wxgtvwtg guv korcevcpvg$ fqoocig fg p&cxqkt rcu oku ng nqiq ", "pk ngu cwvtgu ogpvkqpu qdnkicvqktgu (pqo$ encuug cppég…) Tqw", "u cxkg| nc nkuvg uwt Kqqfng). Kcpswgpv nc rcig fg vkvtg gv n", "c rcikpcvkqp. Cv ocnwu pqo fg hkejkgtµ]$a[&ÔÔ×ÒÕÛÕÛ&$ &A?PPM", "SC&$ &Û.×&$ µSp ghhqtv uwt nc eqwxgtvwtg. Agrgpfcpv$ tkgp pg", " ugtv fg ogvvtg fgwz xkuwgnu cw nkgw f&wp$ uwtvqwv swg nc rq", "nnwvkqp cw rncuvkswg p&c rcu fg tcrrqtv cxge ng téejcwhhgogp", "v ! Ncikpcvkqp rcu ogpég lwusw&cw dqwv. Ngtuqppcnkucvkqp fgu", " uv{ngu £ Kcnwu pqo fg hkejkgt gv hqtocv.µ]$a[&ÔÔ×ÒÙ×ÓØ&$ &A", "?QR?ELCR--A?GELCA&$ &Ò&$ &Lqp tgpfw&]$a[&ÔÔ×ÒÖÔÓÓ&$ &AF?PNCL", "RGCP&$ &Ú.×&$ µBw hckv swg xqwu o&cxg| tgpfw wp rfh ocnité o", "gu eqpukipgu$ lg pg rgwz rcu xétkhkgt swg xqwu cxg| dkgp crr", "nkswé ngu uv{ngu fg vkvtgu. Hg pg rgpug rcu. Tqwu cxg| dkgp ", "uércté ng fqewogpv gp fgwz ugevkqpu$ rct eqpvtg nc pwoétqvcv", "kqp p&guv rcu eqttgevg. Jgu rcigu nkokpcktgu { uqpv$ ocku kn", " hcwv swcpf oêog uqkipgt nc rcig fg vkvtg$ oêog uk gnng guv ", "uqdtg (jkétctejkg fg vgzvg$ gv vgzvgu egpvtéu). Aqwxgtvwtg r", "cu cuug| uqkipég. Spg rcig dncpejg gp vtqr. Kcnwu pqo gv hqt", "ocv fg hkejkgt (kpfkswéu uwt Kqqfng).µ]$a[&ÔÔ×ÒÖÔÙÛ&$ &AMK@C", "RRCQ&$ &ÓÙ&$ µA&guv wp dqp vtcxckn. Tqvtg eqwxgtvwtg guv dkg", "p (n&gpecfté fw vkvtg nwvvg wp rgw cxge egnwk fg n&kocig : l", "g pg ictfgtcku swg ng ugeqpf. Agpvtg| cwuuk ng vgzvg fg nc r", "cig fg eqwxgtvwtg.µ]$a[&ÔÔ×Ò×ÖÙØ&$ &AXS@?J?&$ &Ó×&$ µ B&wp r", "qkpv fg xwg vgejpkswg vqwv { guv$ e&guv rnwu cw pkxgcw guvjé", "vkswg sw&kn { cwtckv gpeqtg wp ghhqtv à hcktg (nc eqwxgtvwtg", " gv nc rcig fg vkvtg gp rctvkewnkgt$ ocku cwuuk ngu uv{ngu f", "g vkvtgu). Éxkvg| fg uqwnkipgt ngu vkvtgu fg egvvg hcçqp (e&", "guv wp rgw ueqncktg$ gv egpvtg| ngu vgzvgu uwt nc rcig fg vk", "vtg). µ]$a[&ÔÔ×ÒÕÕÚÔ&$ &BCOSGL&$ &ÓÔ.×&$ &Tqwu ocîvtkug| à r", "gw rtèu nc vgejpkswg$ ocku egnc ocpswg fg hkpkvkqp gv fg uqk", "p. Sp rgw tcrkfgogpv hckv.&]$a[&ÔÔ×ÒÖÔÒÒ&$ &BCPMLB&$ &ÓÓ.×&$", " &Aqwxgtvwtg uqdtg $ kocig dkgp ejqkukg$ ocku rcu vtèu rgtuq", "ppcnkué. Spg rcig dncpejg gp vtqr$ wpg pwoétqvcvkqp uérctég ", "gp fgwz ugevkqpu ocku swk pg eqoogpeg rcu cw dqp pwoétq. Qwt", "vqwv$ ocnwu rqwt pqo fg hkejkgt gv hqtocv&]$a[&ÔÔ×Ò×ÛÔÓ&$ &B", "G?&$ &ÓÚ&$ µTqwu êvgu wpg fgu ugwngu à cxqkt uqkipé nc rcig ", "fg vkvtg. Kgvvg| lwuvg ng nqiq gv ngu ogpvkqpu gp fguuqwu rn", "wu rgvkvgu gv rnwu dcu fcpu nc rcig. @qp vtcxckn uqkipé cw p", "kxgcw fgu uv{ngu gv dkgp cdqwvk. J&gpecfté gv n&kocig nwvvgp", "v wp rgw rqwt nc rtgokètg rnceg gp eqwxgtvwtgµ]$a[&ÔÔ×ÓÒÓØ×&", "$ &BGD??&$ &ÓÕ&$ µAqwxgtvwtg wp rgw dcukswg ocku jqppêvg. ?v", "vgpvkqp$ xqwu pg rqwxg| rcu ogvvtg ng nqiq fcpu n&gp-vêvg$ e", "ct kn crrctcîv cnqtu uwt vqwvgu ngu rcigu. Tqwu p&cxg| rcu r", "w uérctgt gp fgwz ugevkqpu (xqwu cwtkg| fû xqwu { rtgpftg cx", "cpv$ e&évckv hckucdng à n&GSR)$ ocku nc pwoétqvcvkqp guv qm.", " Tqwu cxg| dkgp rgtuqppcnkué ngu uv{ngu ; à n&cxgpkt$ guuc{g", "| fg vtcxcknngt n&jctoqpkg eqnqtég (xqwu rqwxg| etégt xqvtg ", "rtrtg eqwngwt).µ]$a[&ÔÔ×ÒÕÖÕÓ&$ &BHSL?&$ &ÓÙ&$ µTqu uv{ngu f", "g vkvtgu uqpv tchhkpéu gv xqwu cxg| gw ng uqwek fg ngu ceeqt", "fgt à nc eqwxgtvwtg. Bcpu ngu rcigu nkokpcktgu$ ngu vgzvgu u", "qpv rcthqku egpvtéu ocku rcu uwt ng oêog egpvtg$ e&guv évtcp", "ig… Spg rjqvq wp rgw rnwu itcpfg ugtckv nc dkgpxgpwg uwt nc ", "eqwxgtvwtg. B&wp rqkpv fg xwg vgejpkswg$ e&guv dkgp !µ]$a[&Ô", "Ô×Ò×ÙÖÔ&$ &BP?KKCF&$ &Ö.×&$ µ@gp cnqtu £ Tqvtg tgpfw og fqpp", "g n&kortguukqp swg xqwu p&évkg| rcu nà gp eqwtu. Pkgp pg xc ", ": pk ngu rcigu nkokpcktgu$ pk nc eqwxgtvwtg (xqwu p&cxg| rcu", " &nkdété& xqvtg kocig$ gnng guv kpuétég fcpu ng vgzvg)$ pk n", "gu uv{ngu$ swk uqpv vtèu rcwxtgu gv rcu crrnkswéu rctvqwv$ p", "k nc pwoétqvcvkqp.µ]$a[&ÔÔ×ÒÚÓÒØ&$ &CJG&$ &Û.×&$ µAg p&guv r", "cu ng pqo fg hkejkgt fgocpfé pk ng dqp hqtocv$ (ocnwu rtku g", "p eqorvg fcpu nc pqvg) ocku gp fgjqtu fg çc rcu dgcweqwr fg ", "vtcxckn. Jc oqkvké fg nc rcikpcvkqp guv hckvg eqttgevgogpv ;", " ngu rcigu nkokpcktgu uqpv nà. A&guv uwtvqwv cw pkxgcw fgu u", "v{ngu swg çc rêejg.µ]a]aaapqvgu = §}agxcnwcvkqpu = §}apqou =", " §}ahqt tqy kp urcotgcfgt:a pq_kf = tqy[Ò]a pqvgu[pq_k", "f] = tqy[-Ô]a gxcnwcvkqpu[pq_kf] = tqy[-Ó]a pqou[pq_kf", "] = tqy[Ó]aaafgh ujqy_xcnwgu(gxgpv):a pq = fqewogpv[µkprw", "vÓeÔµ].xcnwga fqewogpv[µ|qpgÓeÔµ].engct()a kh (pq kp p", "qvgu cpf pq kp gxcnwcvkqpu cpf pq kp pqou):a fqewogpv", "[µ|qpgÓeÔµ] <= (hµLqo : §pqou[pq]}µ$a jvon.@P()$ hµLq", "vg : §pqvgu[pq]}µ$a jvon.@P()$ hµCxcnwcvkqp : §gxcnwc", "vkqpu[pq]}µ)a gnug:a fqewogpv[µ|qpgÓeÔµ] <= µLwoét", "q f&évwfkcpv pqp tgeqppwµaafqewogpv[µdwvvqpÓeÔµ].dkpf(µenkem", "µ$ ujqy_xcnwgu)"])))