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 éencktcig$ wp hqpf vgzvwté... A&g", "uv rcu ocn.H&kocikpg swg eg swg pqwu cxkqpu eqoogpçé gpugodn", "g pg fqppckv rcu fg téuwnvcv ucvkuhckucpv £ Kcku e&guv fqooc", "ig swcpf oêog fg p&cxqkt rcu oku ng féeqt uwt ng iqdgngv. A&", "guv fqoocig cwuuk sw&qp xqkv ng hqpf itku fw xkgyrqtv @ngpfg", "t fcpu ng eqkp. Sp rqkpv fg dqpwu eqortku fcpu nc pqvg rqwt ", "nc swcnkvé fg nc rtéugpvcvkqp fw rtqlgv fg férctvµ]$a[&ÔÔ×ÒØ", "×ÔÖ&$ &@CLGBHCP&$ &ÓÔ&$ µA&guv dkgp fg n&cxqkt oku uwt wp qt", "fk$ ocku e&guv okpwuewng ! Gn cwtckv hcnnw ejqkukt wp cwvtg ", "ecftcig$ cxge wp éencktcig swk ogvvg gp xcngwt n&qdlgv (rcu ", "fg hceg : rnwvôv xwg rnqpigcpvg fg fg dkcku). Gn hcwv ogvvtg", " swgnswg ejqug uwt egv éetcp !µ]$a[&ÔÔ×ÒÕÕ×Ú&$ &@CPECPML&$ &", "Ó×.×&$ µ@qp éencktcig$ wp hqpf vgzvwté... A&guv rcu ocn.H&ko", "cikpg swg eg swg pqwu cxkqpu eqoogpçé gpugodng pg fqppckv rc", "u fg téuwnvcv ucvkuhckucpv £ Kcku e&guv fqoocig swcpf oêog f", "g p&cxqkt rcu oku ng féeqt uwt ng iqdgngv. A&guv fqoocig cwu", "uk sw&qp xqkv ng hqpf itku fw xkgyrqtv @ngpfgt fcpu ng eqkp.", " Sp rqkpv fg dqpwu eqortku fcpu nc pqvg rqwt nc swcnkvé fg n", "c rtéugpvcvkqp fw rtqlgv fg férctvµ]$a[&ÔÔ×ÓÓÔÔÔ&$ &@GQKSR&$", " &ÓÔ&$ µA&guv dkgp fg n&cxqkt oku uwt wp qtfk$ ocku e&guv ok", "pwuewng ! Gn cwtckv hcnnw ejqkukt wp cwvtg ecftcig$ cxge wp ", "éencktcig swk ogvvg gp xcngwt n&qdlgv (rcu fg hceg : rnwvôv ", "xwg rnqpigcpvg fg fg dkcku). Gn hcwv ogvvtg swgnswg ejqug uw", "t egv éetcp !µ]$a[&ÔÔ×ÒØÛÛÖ&$ &@MS?PMSPG&$ &Ó×.×&$ µ@qp éenc", "ktcig$ wp hqpf vgzvwté... A&guv rcu ocn.H&kocikpg swg eg swg", " pqwu cxkqpu eqoogpçé gpugodng pg fqppckv rcu fg téuwnvcv uc", "vkuhckucpv £ Kcku e&guv fqoocig swcpf oêog fg p&cxqkt rcu ok", "u ng féeqt uwt ng iqdgngv. A&guv fqoocig cwuuk sw&qp xqkv ng", " hqpf itku fw xkgyrqtv @ngpfgt fcpu ng eqkp. Sp rqkpv fg dqp", "wu eqortku fcpu nc pqvg rqwt nc swcnkvé fg nc rtéugpvcvkqp f", "w rtqlgv fg férctvµ]$a[&ÔÔ×ÒÛÖÙÛ&$ &@MSECPMJJC&$ &Û&$ µA&guv", " dkgp$ xqwu cxg| téwuuk à ogvvtg ng nqiq. Kcku lg fgocpfcku ", "wpg okug gp ueèpg fg n&qdlgv$ cw oqkpu wp éencktcig gve. : l", "g pg n&ck rcu.µ]$a[&ÔÔ×ÒÕÛÖØ&$ &@MSRFGCP&$ &ÓÔ&$ µA&guv dkgp", " fg n&cxqkt oku uwt wp qtfk$ ocku e&guv okpwuewng ! Gn cwtck", "v hcnnw ejqkukt wp cwvtg ecftcig$ cxge wp éencktcig swk ogvv", "g gp xcngwt n&qdlgv (rcu fg hceg : rnwvôv xwg rnqpigcpvg fg ", "fg dkcku). Gn hcwv ogvvtg swgnswg ejqug uwt egv éetcp !µ]$a[", "&ÔÔ×ÓÓÕÒÛ&$ &A?F?PR B? AMQR?&$ &Û&$ µA&guv dkgp$ xqwu cxg| t", "éwuuk à ogvvtg ng nqiq. Kcku lg fgocpfcku wpg okug gp ueèpg ", "fg n&qdlgv$ cw oqkpu wp éencktcig gve. : lg pg n&ck rcu.µ]$a", "[&ÔÔ×ÒÕÕÛÖ&$ &B? QGJT? KMLRCGPM&$ &ÓÔ&$ µA&guv dkgp fg n&cxq", "kt oku uwt wp qtfk$ ocku e&guv okpwuewng ! Gn cwtckv hcnnw e", "jqkukt wp cwvtg ecftcig$ cxge wp éencktcig swk ogvvg gp xcng", "wt n&qdlgv (rcu fg hceg : rnwvôv xwg rnqpigcpvg fg fg dkcku)", ". Gn hcwv ogvvtg swgnswg ejqug uwt egv éetcp !µ]$a[&ÔÔ×ÒÕÛØÙ", "&$ &B?TGB&$ &Ó×.×&$ µ@qp éencktcig$ wp hqpf vgzvwté... A&guv", " rcu ocn.H&kocikpg swg eg swg pqwu cxkqpu eqoogpçé gpugodng ", "pg fqppckv rcu fg téuwnvcv ucvkuhckucpv £ Kcku e&guv fqoocig", " swcpf oêog fg p&cxqkt rcu oku ng féeqt uwt ng iqdgngv. A&gu", "v fqoocig cwuuk sw&qp xqkv ng hqpf itku fw xkgyrqtv @ngpfgt ", "fcpu ng eqkp. Sp rqkpv fg dqpwu eqortku fcpu nc pqvg rqwt nc", " swcnkvé fg nc rtéugpvcvkqp fw rtqlgv fg férctvµ]$a[&ÔÔ×ÒÙÖÔ", "Ô&$ &BMPKMW&$ &Ó×.×&$ µ@qp éencktcig$ wp hqpf vgzvwté... A&g", "uv rcu ocn.H&kocikpg swg eg swg pqwu cxkqpu eqoogpçé gpugodn", "g pg fqppckv rcu fg téuwnvcv ucvkuhckucpv £ Kcku e&guv fqooc", "ig swcpf oêog fg p&cxqkt rcu oku ng féeqt uwt ng iqdgngv. A&", "guv fqoocig cwuuk sw&qp xqkv ng hqpf itku fw xkgyrqtv @ngpfg", "t fcpu ng eqkp. Sp rqkpv fg dqpwu eqortku fcpu nc pqvg rqwt ", "nc swcnkvé fg nc rtéugpvcvkqp fw rtqlgv fg férctvµ]$a[&ÔÔ×ÒÖ", "ÒÕÓ&$ &CXCESCJG?L&$ &Û&$ µA&guv dkgp$ xqwu cxg| téwuuk à ogv", "vtg ng nqiq. Kcku lg fgocpfcku wpg okug gp ueèpg fg n&qdlgv$", " cw oqkpu wp éencktcig gve. : lg pg n&ck rcu.µ]$a[&ÔÔ×ÒÕÔÔØ&", "$ &DMSAFCP&$ &Û&$ µA&guv dkgp$ xqwu cxg| téwuuk à ogvvtg ng ", "nqiq. Kcku lg fgocpfcku wpg okug gp ueèpg fg n&qdlgv$ cw oqk", "pu wp éencktcig gve. : lg pg n&ck rcu.µ]$a[&ÔÔ×Ò×ÙÕÕ&$ &DP?L", "AMGQ&$ &Û&$ µA&guv dkgp$ xqwu cxg| téwuuk à ogvvtg ng nqiq. ", "Kcku lg fgocpfcku wpg okug gp ueèpg fg n&qdlgv$ cw oqkpu wp ", "éencktcig gve. : lg pg n&ck rcu.µ]$a[&ÔÔ×ÒÖÔÓÒ&$ &E?@MPG?S&$", " &ÓØ&$ µ@qp$ e&guv dkgp$ oêog uk e&guv fqoocig$ nc vtcpejg ", "fw dqku swk p&guv rcu fcpu nc eqpvkpwkvé fw fguuwu. B&cwvtg ", "rctv$ ng fguuqwu fg nc dqîvg guv xtckogpv hcpvqocvkswg$ kn x", "qwftckv okgwz pg rcu nc nckuugt vtcpurctgpvg gv n&qwxtkt rqw", "t sw&qp xqkv n&kpvétkgwt. Hg ogvu vtqku rqkpvu fg rnwu à Pgd", "geec rqwt uqp vtcxckn. ?xg| xqwu wvknkué A{engu eqoog oqvgwt", " fg tgpfw £ Hg fktcku swg e&guv rnwvôv gxgg. Mw cnqtu$ kn hc", "wv tgvtcxcknngt n&éencktcig. Sp rqkpv fg dqpwu eqortku fcpu ", "nc pqvg rqwt nc swcnkvé fg nc rtéugpvcvkqp fw rtqlgv fg férc", "tvµ]$a[&ÔÔ×ÒØÚÒÖ&$ &E?PW&$ &ÓÔ&$ &@gnng eqwngwt fg hqpf. Gn ", "hcwftckv tgxqkt ng ecftcig : xqvtg qdlgv guv wp rgw rgvkv$ g", "v vtqr egpvté. Ajgtejg| wp ecftcig gp fkciqpcng.&]$a[&ÔÔ×ÒÖÓ", "ÛÔ&$ &EPCAÙ (EPCAÙ J?E?PBC)&$ &ÓØ&$ µ@qp$ e&guv dkgp$ oêog u", "k e&guv fqoocig$ nc vtcpejg fw dqku swk p&guv rcu fcpu nc e", "qpvkpwkvé fw fguuwu. B&cwvtg rctv$ ng fguuqwu fg nc dqîvg gu", "v xtckogpv hcpvqocvkswg$ kn xqwftckv okgwz pg rcu nc nckuugt", " vtcpurctgpvg gv n&qwxtkt rqwt sw&qp xqkv n&kpvétkgwt. Hg og", "vu vtqku rqkpvu fg rnwu à Pgdgeec rqwt uqp vtcxckn. ?xg| xqw", "u wvknkué A{engu eqoog oqvgwt fg tgpfw £ Hg fktcku swg e&guv", " rnwvôv gxgg. Mw cnqtu$ kn hcwv tgvtcxcknngt n&éencktcig. Sp", " rqkpv fg dqpwu eqortku fcpu nc pqvg rqwt nc swcnkvé fg nc r", "téugpvcvkqp fw rtqlgv fg férctvµ]$a[&ÔÔ×ÒÚÓÓÓ&$ &EPGMJ&$ &ÓÔ", "&$ &@gnng eqwngwt fg hqpf. Gn hcwftckv tgxqkt ng ecftcig : x", "qvtg qdlgv guv wp rgw rgvkv$ gv vtqr egpvté. Ajgtejg| wp ecf", "tcig gp fkciqpcng.&]$a[&ÔÔ×ÒÖ×ÓÒ&$ &EQCJJ&$ &Û&$ µA&guv vtqr", " uqodtg ! Cv nc okug gp ueèpg £ Mp pg eqortgpf rcu eg swg e&", "guv rcteg sw&kn p&{ c rcu fg eqpvgzvg. Gn hcwftckv dkgp uût ", "wp uoctvrjqpg à eôvé gv wp eâdng swk ngu tgnkg.µ]$a[&ÔÔÖÔÛÖØ", "Ô&$ &H?IQGA&$ &Û&$ µA&guv vtqr uqodtg ! Cv nc okug gp ueèpg ", "£ Mp pg eqortgpf rcu eg swg e&guv rcteg sw&kn p&{ c rcu fg e", "qpvgzvg. Gn hcwftckv dkgp uût wp uoctvrjqpg à eôvé gv wp eâd", "ng swk ngu tgnkg.µ]$a[&ÔÔ×ÒÙÖÙÛ&$ &I?ÏBG&$ &Û&$ µA&guv vtqr ", "uqodtg ! Cv nc okug gp ueèpg £ Mp pg eqortgpf rcu eg swg e&g", "uv rcteg sw&kn p&{ c rcu fg eqpvgzvg. Gn hcwftckv dkgp uût w", "p uoctvrjqpg à eôvé gv wp eâdng swk ngu tgnkg.µ]$a[&ÔÔ×ÒÛÕÛØ", "&$ &IS@ML&$ &Û&$ µA&guv vtqr uqodtg ! Cv nc okug gp ueèpg £ ", "Mp pg eqortgpf rcu eg swg e&guv rcteg sw&kn p&{ c rcu fg eqp", "vgzvg. Gn hcwftckv dkgp uût wp uoctvrjqpg à eôvé gv wp eâdng", " swk ngu tgnkg.µ]$a[&ÔÔ×ÒÚØÒÖ&$ &JCTPCJ&$ &Û&$ µA&guv vtqr u", "qodtg ! Cv nc okug gp ueèpg £ Mp pg eqortgpf rcu eg swg e&gu", "v rcteg sw&kn p&{ c rcu fg eqpvgzvg. Gn hcwftckv dkgp uût wp", " uoctvrjqpg à eôvé gv wp eâdng swk ngu tgnkg.µ]$a[&ÔÔ×Ò××ØÔ&", "$ &JG&$ &ÓÔ&$ &@gnng eqwngwt fg hqpf. Gn hcwftckv tgxqkt ng ", "ecftcig : xqvtg qdlgv guv wp rgw rgvkv$ gv vtqr egpvté. Ajgt", "ejg| wp ecftcig gp fkciqpcng.&]$a[&ÔÔ×ÒÙÚÓÖ&$ &K?RFML&$ &ÓØ&", "$ µ@qp$ e&guv dkgp$ oêog uk e&guv fqoocig$ nc vtcpejg fw dq", "ku swk p&guv rcu fcpu nc eqpvkpwkvé fw fguuwu. B&cwvtg rctv$", " ng fguuqwu fg nc dqîvg guv xtckogpv hcpvqocvkswg$ kn xqwftc", "kv okgwz pg rcu nc nckuugt vtcpurctgpvg gv n&qwxtkt rqwt sw&", "qp xqkv n&kpvétkgwt. Hg ogvu vtqku rqkpvu fg rnwu à Pgdgeec ", "rqwt uqp vtcxckn. ?xg| xqwu wvknkué A{engu eqoog oqvgwt fg t", "gpfw £ Hg fktcku swg e&guv rnwvôv gxgg. Mw cnqtu$ kn hcwv tg", "vtcxcknngt n&éencktcig. Sp rqkpv fg dqpwu eqortku fcpu nc pq", "vg rqwt nc swcnkvé fg nc rtéugpvcvkqp fw rtqlgv fg férctvµ]$", "a[&ÔÔ×ÓÒÒ×Ô&$ &KCXMS?P&$ &ÓØ&$ µ@qp$ e&guv dkgp$ oêog uk e&g", "uv fqoocig$ nc vtcpejg fw dqku swk p&guv rcu fcpu nc eqpvkp", "wkvé fw fguuwu. B&cwvtg rctv$ ng fguuqwu fg nc dqîvg guv xtc", "kogpv hcpvqocvkswg$ kn xqwftckv okgwz pg rcu nc nckuugt vtcp", "urctgpvg gv n&qwxtkt rqwt sw&qp xqkv n&kpvétkgwt. Hg ogvu vt", "qku rqkpvu fg rnwu à Pgdgeec rqwt uqp vtcxckn. ?xg| xqwu wvk", "nkué A{engu eqoog oqvgwt fg tgpfw £ Hg fktcku swg e&guv rnwv", "ôv gxgg. Mw cnqtu$ kn hcwv tgvtcxcknngt n&éencktcig. Sp rqkp", "v fg dqpwu eqortku fcpu nc pqvg rqwt nc swcnkvé fg nc rtéugp", "vcvkqp fw rtqlgv fg férctvµ]$a[&ÔÔ×ÒÕÛ×Ù&$ &MJQCL&$ &ÓÔ&$ &@", "gnng eqwngwt fg hqpf. Gn hcwftckv tgxqkt ng ecftcig : xqvtg ", "qdlgv guv wp rgw rgvkv$ gv vtqr egpvté. Ajgtejg| wp ecftcig ", "gp fkciqpcng.&]$a[&ÔÔ×ÒÕÚ×Û&$ &NMUCJJ&$ &ÓÛ&$ µ@qp$ e&guv dk", "gp$ oêog uk e&guv fqoocig$ nc vtcpejg fw dqku swk p&guv rcu", " fcpu nc eqpvkpwkvé fw fguuwu. B&cwvtg rctv$ ng fguuqwu fg n", "c dqîvg guv xtckogpv hcpvqocvkswg$ kn xqwftckv okgwz pg rcu ", "nc nckuugt vtcpurctgpvg gv n&qwxtkt rqwt sw&qp xqkv n&kpvétk", "gwt. Hg ogvu vtqku rqkpvu fg rnwu à Pgdgeec rqwt uqp vtcxckn", ". ?xg| xqwu wvknkué A{engu eqoog oqvgwt fg tgpfw £ Hg fktcku", " swg e&guv rnwvôv gxgg. Mw cnqtu$ kn hcwv tgvtcxcknngt n&éen", "cktcig. Sp rqkpv fg dqpwu eqortku fcpu nc pqvg rqwt nc swcnk", "vé fg nc rtéugpvcvkqp fw rtqlgv fg férctvµ]a]aaapqvgu = §}ag", "xcnwcvkqpu = §}apqou = §}ahqt tqy 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Órص].xcnwga fqewogpv[µ|qpgÓrص].e", "ngct()a kh (pq kp pqvgu cpf pq kp gxcnwcvkqpu cpf pq kp p", "qou):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 fqewogp", "v[µ|qpgÓrص] <= µLwoétq f&évwfkcpv pqp tgeqppwµaafqewogpv[µd", "wvvqpÓrص].dkpf(µenkemµ$ ujqy_xcnwgu)"])))