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?&$ &Ó×&$ µ@kgp ! Tqwu cdwug| wp rgw fgu « l&ck rw",
" » gv uetqnng| wp rgw vtqr à n&éetcp$ ocku e&guv fw dqp vtcx",
"ckn. Etcrjkuog qm$ nkgp qm. Bqoocig fg p&cxqkt rcu kpvéité n",
"c xkféq fktgevgogpv fcpu ng ukvg ygd ocku uqwu hqtog fg nkgp",
".µ]$a[&ÔÔÖÒÚÚÕÔ&$ &@MCA?QQC-D?PGEMSV&$ &ÓÕ&$ µJc xkféq p&guv",
" rcu ocn$ dkgp swg xqwu p&c{g| rcu gzrnkswé rct gzgorng eg s",
"w&guv nc féoctejg rqtvhqnkq gv wpg Q?É. Bqoocig cwuuk fg pg ",
"rcu n&cxqkt kpvéité fktgevgogpv gp xkféq. Jg itcrjkuog guv q",
"m$ ng nkgp { guv ocku xqwu p&êvgu rcu cnnég uwt nc rcig f&ce",
"ewgkn$ eg swk hckv sw&kn guv vtèu nqpi gv dk|cttg. -Ô rqkpvu",
" rqwt ng tgvctf (kpenwu)µ]$a[&ÔÔÖÒÕ×ÔÚ&$ &A?QQGCP&$ &Ó×&$ µJ",
"g uqp guv wp rgw dcu$ gv egnc ogv fw vgoru à féocttgt. Jg tg",
"uvg guv dkgp. Kcku lg pg eqortgpfu rcu rqwtswqk xqwu p&cxg| ",
"rcu kpvéité nc xkféq fktgevgogpv uwt ng ukvg$ rwkuswg xqwu c",
"xg| uw ng hcktg uwt f&cwvtgu xkféqu.Etcrjkuog qm. µ]$a[&ÔÔÖÒ",
"ÖÚÕ×&$ &AJ?P? QGKMCQ&$ &Ó×&$ µJg nkgp xgtu xqvtg ukvg ygd p&",
"guv rcu ng dqp ! Qkpqp$ nc xkféq guv dkgp (uwtvqwv ng uqp)$ ",
"wp rgw vtqr nqpiwg.Etcrjkuog qmµ]$a[&ÔÔÖÒÓÙÚÔ&$ &AWNPGCL A?J",
"MPC&$ &&$ &&]$a[&ÔÔÖÒÔÙÔ×&$ &BSKMLR&$ &ÓØ&$ µ@kgp rqwt ng eq",
"pvgpw ! Tqwu cxg| hckv à nc hqku eqwtv gv ghhkeceg. Etcrjkuo",
"g qm. Gn ocpswg lwuvg ng nkgp xgtu ng ukvg ygd$ gv ucpu egnw",
"k-ek$ rcu f&kpfgzcvkqp rct Eqqing.µ]$a[&ÔÔÖÒÖÓÙÙ&$ &BSPAFML&",
"$ &Ó×&$ µ@kgp rqwt ng eqpvgpw$ itcrjkuog qm$ nkgp xgtu ng uk",
"vg qm. Hg tgitgvvg lwuvg swg xqwu p&c{kg| rcu kpvéité nc xkf",
"éq fktgevgogpv fcpu ng ukvg eqoog lg n&cxcku fgocpfé$ ocku r",
"ct wp nkgp (uwt ng oqv kek$ gp rnwu). Ó rqkpv gp oqkpu rqwt ",
"nc xkféq pqp térgtvqtkég.µ]$a[&ÔÔÖÒØ×××&$ &CQR?@JCR&$ &ÓÙ$×&",
"$ µJ&gpugodng guv dkgp ocîvtkué gv eqorngv (itcrjkuog$ nkgpu",
"$ kpvéitcvkqp cw ukvg$ eqpvgpw fg nc xkféq). Ngwv-êvtg wp vq",
"wv rgvkv rgw vtqr nqpi.µ]$a[&ÔÔÖÒÔÕÛÔ&$ &E?LBML&$ &ÓÔ$×&$ &B",
"gu jéukvcvkqpu fcpu nc xkféq$ fgu jgw$ fqpe$cnqtu gpuwkvg$ f",
"gu dncpeu$ rcu cuug| rtércté. Gpvéitcvkqp dcppkètg gv nqiq o",
"kpkocng&]$a[&ÔÔÖÓÔÔØÓ&$ &EGJJCR&$ &ÓÒ&$ µQctcj$ kn pg hcwv r",
"cu févcknngt ng eqpvgpw fgu ctvkengu gve ! A&guv rqwt çc swg",
" e&guv uk nqpi ! Gn ocpswg cwuuk ng nkgp xgtu xqvtg ukvg ygd",
". Gn hcwftckv ogvvtg nc xkféq fktgevgogpv fcpu ng ukvg ygd.µ",
"]$a[&ÔÔÖÒÖØÓÙ&$ &EMPGCS&$ &Ò&$ &Ncu fg xkféq&]$a[&ÔÔÖÓÚÖ×Ù&$",
" &EMSGL&$ &ÓØ$×&$ µ@kgp rqwt ng eqpvgpw$ rqwt ngswgn xqwu cx",
"g| oêog hckv wp rgw fg oqpvcig. Etcrjkuog qm (xqwu rqwttkg| ",
"ogvvtg lwuvg n&crrctgkn rjqvq eqoog nqiq$ eqoog rqwt n&keôpg",
" fw ukvg).$ nkgp xgtu ng ukvg qm. Hg tgitgvvg lwuvg swg xqwu",
" p&c{kg| rcu kpvéité nc xkféq fktgevgogpv fcpu ng ukvg eqoog",
" lg n&cxcku fgocpfé$ ocku rct wp nkgp (uwt ng oqv kek$ gp rn",
"wu).µ]$a[&ÔÔÖÒÔÚÖÖ&$ &F?LJML-@?JRSQ&$ &ÓÕ$×&$ µ@qppg xkféq$ ",
"itcrjkuog qm (kn ocpswg ng vjèog fw dnqi uwt nc dcppkètg swc",
"pf oêog). Bqoocig fg p&cxqkt rcu kpvéité nc xkféq fktgevgogp",
"v fcpu ng ukvg ygd ocku uqwu hqtog fg nkgp.Ó rqkpv gp oqkpu ",
"rqwt nc xkféq pqp térgtvqtkég.µ]$a[&ÔÔÖÒÕÚÒÒ&$ &J?DCPPCPC&$ ",
"&Ó×$×&$ µTqwu jéukvg| dgcweqwr à n&qtcn gv egnc fkurctcîvtck",
"v uk xqwu térévkg| fcxcpvcig. Nct-eqpvtg$ xqwu êvgu wp fgu u",
"gwnu à xqwu êvtg kpvéité xkuwgnngogpv à xqvtg xkféq$ e&guv w",
"p rnwu. Jc dcppkètg gv ng nqiq fg nc ejcîpg uqpv dkgp$ ng nk",
"gp xgtu ng ukvg guv rtéugpv. Gn ocpswg nc fguetkrvkqp fg nc ",
"ejcîpg. Ag ugtckv okgwz fg rqwxqkt eqpuwnvgt xqvtg xkféq fkt",
"gevgogpv uwt ng ukvg.µ]$a[&ÔÔÖÒÓÚÚÖ&$ &JGCS&$ &ÓØ$×&$ µTkféq",
" dkgp rtérctég$ eqpenwukqp wp rgw cdtwdvg. @kgp rqwt n&kpvéi",
"tcvkqp fg nc xkféq cw ukvg.µ]$a[&ÔÔÖÒÓÛØÒ&$ &JÉML&$ &Ó×$×&$ ",
"µ@qppg xkféq ! A&guv vqwv fg uwkvg rnwu kpvétguucpv$ swcpf o",
"êog$ swcpf qp pg xqkv rcu swg ng ukvg ygd. Tqwu rcuug| wp rg",
"w xkvg uwt ng eqpvgpw. Nqwt nc dcppkètg$ ng vjèog fw dnqi qw",
" ng pqo fw ukvg hgtckv fw dkgp.µ]$a[&ÔÔÖÒÔÛÒÕ&$ &K?JMLE?&$ &",
"Û&$ µNtqdnèog : nkgp xgtu nc ejcîpg gv pqp nc xkféq. Fqtu$ n",
"c xkféq p&guv rcu kpvéitég rqwt n&kpuvcpv. Ncu fg nqiq.µ]$a[",
"&ÔÔÖÒÔ×ÔÒ&$ &K?LSIW?L&$ &ÓÙ&$ µ@tcxq$ ng oqpvcig ! Agnc tgpf",
" ngu ejqugu rnwu xkxcpvgu$ oêog uk lg rgpug swg xqwu cwtkg| ",
"fû térévgt fcxcpvcig (dgcweqwr f&jéukvcvkqpu).µ]$a[&ÔÔÖÒÔÖÛÕ",
"&$ &K?XCR&$ &ÓÓ&$ µ@qp$ ng eqpvgpw guv wp rgw ejwejqvé ocku ",
"çc rgwv cnngt) Tqvtg nkgp xgtu xqvtg ukvg ygd p&guv rcu dqp.",
" Spg rgvkvg rjtcug uwt ng ukvg rqwt rtéugpvgt xqvtg xkféq pg",
" ugtckv rcu fg vtqr. Õ rqkpvu gp oqkpu rqwt ng tgvctf gv nc ",
"rqnkvguug swk eqpukuvg à u&gzewugt gv à rtéxgpkt sw&gnng guv",
" nà (kpenwu fcpu nc pqvg).µ]$a[&ÔÔÖÒØ××Ô&$ &KMP?JCQ&$ &Ó×&$ ",
"µKcpswg wp rgw fg térévkvkqpu rtécncdngu$ gv xqwu cxg| qwdnk",
"é ng nqiq fg nc ejcîpg. Jg nkgp guv wp rgw dk|cttg : kn fgxt",
"ckv ug rtéugpvgt fcpu wpg xgtukqp rnwu eqwtvg (kn hcwv ug tg",
"pftg xtckogpv uwt nc rcig f&ceewgkn fg xqvtg ukvg). @kgp$ n&",
"kpvéitcvkqp fg nc ejcîpg uwt ng ukvg.µ]$a[&ÔÔÖÒÛÛÖÚ&$ &Q?SJL",
"GCP&$ &ÓÖ&$ µJc dcppkètg fg nc ejcîpg p&guv rcu vtèu rctncpv",
"g ! Gn cwtckv évé kpvétguucpv f&clqwvgt uwt n&kocig ng vjèog",
" fw dnqi qw ng pqo fw ukvg. Bqoocig fg p&cxqkt rcu kpvéité n",
"c xkféq fktgevgogpv fcpu ng ukvg ygd ocku uqwu hqtog fg nkgp",
".Ó rqkpv gp oqkpu rqwt nc xkféq pqp térgtvqtkég.µ]$a[&ÔÔÔÒ×Ô",
"ÒÕ&$ &QCPPC&$ &ÓÙ&$ µ@qp vtcxckn$ eqoog ng tguvg ! Jc xkféq ",
"guv lwuvg wp rgw nqpiwg dkgp swg ocîvtkuég$ gv l&ck wp rgvkv",
" tgitgv rqwt ng nqiq fg nc ejcîpg : e&guv fqoocig sw&kn uqkv",
" eqwré.µ]$a[&ÔÔÖÒÓÛÚÕ&$ &RFCTCLGL&$ &ÓÔ&$ µTqvtg vqp guv wp ",
"rgw oqpqvqpg$ ocku xqwu cxg| rtércté gv térévé. Gn ocpswg ng",
" pqo fw ukvg qw ng vjèog fw dnqi uwt nc dcppkètg {qwvwdg. Jg",
" nqiq$ nwk$ tgpf okgwz swg uwt ng ukvg. Jg rtqdnèog swk xqwu",
" hckv rgtftg fgu rqkpvu : kn p&{ c rcu ng nkgp xgtu ng ukvg.",
"µ]$a[&ÔÔÖÓÒÚÚÕ&$ &RFGTCP&$ &Û&$ µTqwu cxg| fg n&ckucpeg à n&",
"qtcn$ fqoocig fg pg rcu okgwz n&wvknkugt : gpugodng vtqr kor",
"tqxkué. Gn ocpswg ng nkgp xgtu ng ukvg ygd. Ag ugtckv okgwz$",
" cwuuk$ fg ogvvtg xqvtg xkféq uwt ng ukvg cw nkgw fg ogvvtg ",
"wp nkgp.µ]$a[&ÔÔÖÒ×Ô×Û&$ &RPSDDCPR&$ &ÓÕ&$ µNcu ocn nc xkféq",
"$ dkgp ng itcrjkuog. Õ rqkpvu gp oqkpu rqwt ng tgvctf gv nc ",
"rqnkvguug swk eqpukuvg à u&gzewugt gv à rtéxgpkt sw&gnng guv",
" nà (kpenwu fcpu nc pqvg).µ]$a[&ÔÔÖÒØÒÚÒ&$ &TGPGCSV--@?PAXWL",
"QIG&$ &Û&$ µEtcrjkuog qm$ nkgp cwuuk. Aqpvgpw féuqticpkué (x",
"qwu êvgu swk £ Tqwu hckvgu swgnngu évwfgu £ À rtéekugt cw fé",
"dwv fg nc xkféq). ocpswg cduqnw f&gpvjqwukcuog fcpu ng vqp. ",
"Õ rqkpvu gp oqkpu rqwt ng tgvctf gv nc rqnkvguug swk eqpukuv",
"g à u&gzewugt gv à rtéxgpkt sw&gnng guv nà (kpenwu fcpu nc p",
"qvg).µ]]aaapqvgu = §}agxcnwcvkqpu = §}apqou = §}ahqt tqy kp ",
"urcotgcfgt:a    pq_kf = tqy[Ò]a    pqvgu[pq_kf] = tqy[-Ô]a  ",
"  gxcnwcvkqpu[pq_kf] = tqy[-Ó]a    pqou[pq_kf] = tqy[Ó]aaafg",
"h ujqy_xcnwgu(gxgpv):a    pq = fqewogpv[µkprwvÖµ].xcnwga    ",
"fqewogpv[µ|qpgÖµ].engct()a    kh (pq kp pqvgu cpf pq kp gxcn",
"wcvkqpu cpf pq kp pqou):a        fqewogpv[µ|qpgÖµ] <= (hµLqo",
" : §pqou[pq]}µ$a        jvon.@P()$ hµLqvg : §pqvgu[pq]}µ$a  ",
"      jvon.@P()$ hµCxcnwcvkqp : §gxcnwcvkqpu[pq]}µ)a    gnug",
":a        fqewogpv[µ|qpgÖµ] <= µLwoétq f&évwfkcpv pqp tgeqpp",
"wµaafqewogpv[µdwvvqpÖµ].dkpf(µenkemµ$ ujqy_xcnwgu)"])))