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&$ &ÓÙ.ÓÙ&$ µ@qp vtcxckn$ wp rgw rnwu hckdng rqwt",
" nc rctvkg xkuwgnng. Gn pg hcwv rcu jéukvgt à uqnnkekvgt fg ",
"n&ckfg.µ]$a[&ÔÔ×ÒØ×ÔÖ&$ &@CLGBHCP&$ &Õ.ÕÕ&$ µBkhhkekng$ à rc",
"tvkt f&wp oqogpv$ fg tcvvtcrgt ng tgvctf ceewowné.µ]$a[&ÔÔ×Ò",
"ÕÕ×Ú&$ &@CPECPML&$ &ÓÔ.ØÙ&$ µJ&ckt fg tkgp$ kn { cxckv dgcwe",
"qwr fg ejqugu à hcktg rqwt qdvgpkt wpg vtèu dqppg pqvg.Tqwu ",
"p&cxg| rcu fqppé vqwv eg swg xqwu rqwxkg|.µ]$a[&ÔÔ×ÓÓÔÔÔ&$ &",
"@GQKSR&$ &Ö.Ò&$ µNqwtswqk êvgu-xqwu nà$ uk e&guv rqwt pg tkg",
"p hcktg £µ]$a[&ÔÔ×ÒØÛÛÖ&$ &@MS?PMSPG&$ &Ù.×&$ &Kcpswg fg vtc",
"xckn…&]$a[&ÔÔ×ÒÛÖÙÛ&$ &@MSECPMJJC&$ &ÓÙ.Ò&$ &Sp dqp vtcxckn ",
"à vqwu ngu pkxgcwz&]$a[&ÔÔ×ÒÕÛÖØ&$ &@MSRFGCP&$ &ÓØ.×&$ &Sp d",
"qp vtcxckn à vqwu ngu pkxgcwz&]$a[&ÔÔ×ÓÓÕÒÛ&$ &A?F?PR B? AMQ",
"R?&$ &Ú.ÕÕ&$ &Gpuwhhkucpv&]$a[&ÔÔ×ÒÕÕÛÖ&$ &B? QGJT? KMLRCGPM",
"&$ &ÓØ.ØÙ&$ &Cp vtèu dqppg xqkg rqwt ngu ctvkengu$ gv ng tgu",
"vg guv rtguswg rcthckv&]$a[&ÔÔ×ÒÕÛØÙ&$ &B?TGB&$ &ÓØ.ÓÙ&$ &Bg",
"u rgvkvu févcknu à coénkqtgt$ wp vtèu dqp vtcxckn.&]$a[&ÔÔ×Ò",
"ÙÖÔÔ&$ &BMPKMW&$ &ÓÙ.ÓÙ&$ µA&guv wp vtèu dqp vtcxckn.µ]$a[&Ô",
"Ô×ÒÖÒÕÓ&$ &CXCESCJG?L&$ &ÓÔ.ÚÕ&$ &Ncu ocn$ ocku wp rgw kpeqo",
"rngv&]$a[&ÔÔ×ÒÕÔÔØ&$ &DMSAFCP&$ &ÓÖ.Ò&$ &Bqoocig swg ng eqpv",
"gpw pg uwkxg rcu ng tguvg… &]$a[&ÔÔ×Ò×ÙÕÕ&$ &DP?LAMGQ&$ &Ó×.",
"×&$ µJc pcxkicvkqp gv ng eqpvgpw pg uqpv rcu à nc jcwvgwt fw",
" vtcxckn xkuwgn$ ocku e&guv rnwu rct ocpswg fg vgoru sw&cwvt",
"g ejqug.µ]$a[&ÔÔ×ÒÖÔÓÒ&$ &E?@MPG?S&$ &ÓÓ.×&$ µAg swk guv hck",
"v guv dkgp hckv$ ocku eg p&guv rcu eqorngv.µ]$a[&ÔÔ×ÒØÚÒÖ&$ ",
"&E?PW&$ &ÓÕ.ØÙ&$ &Cp rgtfcpv oqkpu fg vgoru cxge xqu xqkukpu",
"$ xqwu cwtkg| qdvgpw wpg cwuuk dqppg pqvg uwt ng eqpvgpw swg",
" uwt ng tguvg. Bqoocig.&]$a[&ÔÔ×ÒÖÓÛÔ&$ &EPCAÙ (EPCAÙ J?E?PB",
"C)&$ &ÓÓ.×&$ &Bqoocig swg eg vtcxckn uqkv kpeqorngv…&]$a[&ÔÔ",
"×ÒÚÓÓÓ&$ &EPGMJ&$ &Ö.ÚÕ&$ &@gcweqwr fg vgoru rgtfw$ gv çc pg",
" ug tcvvtcrg rcu eqoog çc.&]$a[&ÔÔ×ÒÖ×ÓÒ&$ &EQCJJ&$ &Ô.Ò&$ µ",
"Hg pg eqortgpfu rcu swg xqwu pg o&c{g| rcu crrgnég à n&ckfg…",
" Gn p&guv rcu rquukdng uwt wp vtcxckn fg eg igptg$ fg vqwv t",
"gogvvtg cw ngpfgockp.µ]$a[&ÔÔÖÔÛÖØÔ&$ &H?IQGA&$ &ÓÖ.ÓÙ&$ &Ac",
" xc$ ocku xqwu rqwxkg| hcktg okgwz.&]$a[&ÔÔ×ÒÙÖÙÛ&$ &I?ÏBG&$",
" &ÓÔ.ØÙ&$ µTqwu cxkg| ngu ecrcekvéu$ cwuuk dkgp uwt n&curgev",
" itcrjkswg swg uwt ng eqpvgpw$ fg hcktg wp gzegnngpv vtcxckn",
". A&guv fqoocig !µ]$a[&ÔÔ×ÒÛÕÛØ&$ &IS@ML&$ &Ó×.ÓÙ&$ µA&guv w",
"p dqp vtcxckn cxge dgcweqwr fg rgtuqppcnkvé !µ]$a[&ÔÔ×ÒÚØÒÖ&",
"$ &JCTPCJ&$ &ÓÓ.ÚÕ&$ µTqwu rqwxkg| hcktg okgwz$ oêog uk e&gu",
"v wp gpugodng eqttgev.µ]$a[&ÔÔ×Ò××ØÔ&$ &JG&$ &ÓÖ.ØÙ&$ &Tqwu ",
"rqwxkg| hcktg okgwz cw pkxgcw fw eqpvgpw. &]$a[&ÔÔ×ÒÙÚÓÖ&$ &",
"K?RFML&$ &ÓÔ.ÚÕ&$ µFqtoku n&curgev itcrjkswg swk guv vtèu dk",
"gp$ gpugodng oq{gp.µ]$a[&ÔÔ×ÓÒÒ×Ô&$ &KCXMS?P&$ &Ö.×&$ µHg pg",
" eqortgpfu rcu eg swk u&guv rcuué fcpu xqvtg ecu.µ]$a[&ÔÔ×ÒÕ",
"Û×Ù&$ &MJQCL&$ &Û.ÓÙ&$ &Gpeqorngv. Lqwu cxkqpu ng vgoru rqwt",
"vcpv. Bqoocig.&]$a[&ÔÔ×ÒÕÚ×Û&$ &NMUCJJ&$ &ÓÚ.ÚÕ&$ µRtèu dqp ",
"vtcxckn. Jc rctvkg itcrjkswg guv wp rgw vkokfg$ eg p&guv rcu",
" xqvtg rqkpv hqtv. Kcku xqwu vtcxcknng| gv xqwu éeqwvg| eg s",
"w&qp xqwu fkv : eg swk fqppg wp vtcxckn swk eqttgurqpf vqvcn",
"gogpv à nc fgocpfg. @tcxq rqwt egv gpugodng vtèu eqorngv gv ",
"cdqwvkµ]a]aaapqvgu = §}agxcnwcvkqpu = §}apqou = §}ahqt tqy k",
"p urcotgcfgt:a    pq_kf = tqy[Ò]a    pqvgu[pq_kf] = tqy[-Ô]a",
"    gxcnwcvkqpu[pq_kf] = tqy[-Ó]a    pqou[pq_kf] = tqy[Ó]aaa",
"fgh ujqy_xcnwgu(gxgpv):a    pq = fqewogpv[µkprwvÓrÓµ].xcnwga",
"    fqewogpv[µ|qpgÓrÓµ].engct()a    kh (pq kp pqvgu cpf pq k",
"p gxcnwcvkqpu cpf pq kp pqou):a        fqewogpv[µ|qpgÓrÓµ] <",
"= (hµLqo : §pqou[pq]}µ$a        jvon.@P()$ hµLqvg : §pqvgu[p",
"q]}µ$a        jvon.@P()$ hµCxcnwcvkqp : §gxcnwcvkqpu[pq]}µ)a",
"    gnug:a        fqewogpv[µ|qpgÓrÓµ] <= µLwoétq f&évwfkcpv ",
"pqp tgeqppwµaafqewogpv[µdwvvqpÓrÓµ].dkpf(µenkemµ$ ujqy_xcnwg",
"u)"])))