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 = [[&ÔÔÕÒÕ×ØÕ",
"&$ &@?GJJW&$ &ÓØ&$ µBg vtèu dqppgu ejqugu ! Hqnkg eqwxgtvwtg",
"$ dgnngu eqwngwtu. H&ckog dgcweqwr ng xkuwgn uwt ng uqoocktg",
"$ qtkikpcn. @k|cttg egvvg rcig fg vkvtg ucpu jkétctejkg fg v",
"gzvg$ gv gp itkué !µ]$a[&ÔÔÖÒÓÛØÖ&$ &@?SBMR&$ &ÓÔ&$ µA&guv d",
"k|cttg$ fg ecejgt nc oqkvké fw xkuwgn rct eg dcpfgcw itku ! ",
" Qkpqp$ xqvtg uv{ng vkvtg Ó p&guv rcu uwhhkucoogpv fkhhétgpv",
"u fg xqvtg uv{ng vkvtg Ô. qp ug fgocpfg cwuuk rqwtswqk qp pg",
" tgvtqwxg rcu ng xkqngv fg nc eqwxgtvwtg à n&kpvétkgwt fcpu ",
"ngu vkvtgu$ gv rqwtswqk nc rcig fg vkvtg p&guv rcu egpvtég.µ",
"]$a[&ÔÔÖÒÚÓ×Û&$ &@CPLGCP&$ &&$ &LP&]$a[&ÔÔÖÒ×Ø×Ó&$ &@MSFÉPCR",
"&$ &ÓÖ&$ µ@qp vtcxckn f&gpugodng. Kgvvg| vqwlqwtu ngu ceegpv",
"u uwt ngu oclwuewngu$ pg uqwnkipg| rcu ngu vkvtgu (jcdkvwfg ",
"vtèu ueqncktg). Jg uqoocktg rqwttckv ug rcuugt fw uv{ng fg v",
"kvtg Ó. Jg xkuwgn rqwttckv êvtg rnwu itqu gp eqwxgtvwtg gv n",
"g nqiq egpvté fcpu nc rcig fg vkvtg.µ]$a[&ÔÔÖÒÕÚÛÕ&$ &@P?W&$",
" &ÓØ&$ µA&guv vtèu lqnk ! Rtèu tchhkpé. ?vvgpvkqp$ kn { c wp",
"g rcig dncpejg cxcpv ng uqoocktg swk pg fgxtckv rcu êvtg nà.",
"µ]$a[&ÔÔÖÒ×ÓÕÖ&$ &@PCBW&$ &&$ &LP&]$a[&ÔÔÖÒÖÙÕÓ&$ &AFCRR?P&$",
" &Ù&$ µ@qp$ kn p&{ c oêog rcu ngu uv{ngu) H&ck n&kortguukqp ",
"f&cxqkt rgtfw oqp vgoru.µ]$a[&ÔÔÖÒÖÕÖÚ&$ &BCJ?K?PAFC&$ &ÓÕ&$",
" µA&guv wp dqp vtcxckn f&gpugodng$ oêog uk fw rqkpv fg xwg g",
"uvjévkswg kn { cwtckv fgu ejqugu à coénkqtgt : nc eqwxgtvwtg",
" guv wp rgw vtkug$ gnng ocpswg fg eqwngwtu$ kn p&{ c rcu fg ",
"tckuqp swg ng nqiq uqkv gp pqkt gv dncpe. Gn ocpswg nc rcig ",
"fg vkvtg. Jgu vgzvgu uqpv wp rgw ugttéu. Kcku n&guugpvkgn gu",
"v eqortkuµ]$a[&ÔÔÕÒÕÖ×Û&$ &BMQQM&$ &&$ &LP&]$a[&ÔÔÖÒÕÕÔ×&$ &",
"BSKMJGL&$ &ÓÖ&$ µ@qp vtcxckn f&gpugodng. Kgvvg| vqwlqwtu ngu",
" ceegpvu uwt ngu oclwuewngu$ pg uqwnkipg| rcu ngu vkvtgu (jc",
"dkvwfg vtèu ueqncktg). Jg uqoocktg rqwttckv ug rcuugt fw uv{",
"ng fg vkvtg Ó. Jg xkuwgn rqwttckv êvtg rnwu itqu gp eqwxgtvw",
"tg gv ng nqiq egpvté fcpu nc rcig fg vkvtg.µ]$a[&ÔÔÖÒÖÕÓÓ&$ ",
"&CJ K?PBG&$ &ÓÕ&$ µA&guv wp dqp vtcxckn f&gpugodng$ oêog uk ",
"fw rqkpv fg xwg guvjévkswg kn { cwtckv fgu ejqugu à coénkqtg",
"t : nc eqwxgtvwtg guv wp rgw vtkug$ gnng ocpswg fg eqwngwtu$",
" kn p&{ c rcu fg tckuqp swg ng nqiq uqkv gp pqkt gv dncpe. G",
"n ocpswg nc rcig fg vkvtg. Jgu vgzvgu uqpv wp rgw ugttéu. Kc",
"ku n&guugpvkgn guv eqortkuµ]$a[&ÔÔÖÒÓØÓÓ&$ &ECLBPMR&$ &Ó×&$ ",
"µHqnk vtcxckn$ tchhkpé ! Hg rgpug lwuvg swg xqu uqwtegu pg f",
"gxtckgpv rcu êvtg gp xgtv enckt$ e&guv fkhhkekng à nktg. Agn",
"c ocpswg wp rgw f&knnwuvtcvkqpu cw fédwv. Bqoocig$ nc rcikpc",
"vkqp p&guv rcu vqwv à hckv fcpu ngu enqwu.µ]$a[&ÔÔÖÒÖÚÒÓ&$ &",
"EMKCX&$ &ÓÓ&$ µJc eqwxgtvwtg p&guv rcu ocn$ ocku kn ocpswg f",
"gu ogpvkqpu (kn hcwftckv rtéekugt rct gzgorng swg e&guv wpg ",
"u{pvjèug fqewogpvcktg$ gv rtéekugt « uqwu nc fktgevkqp fg Ko",
"g ectfgpcu Kwpq| »). Gn ocpswg fgu rcigu nkokpcktgu$ nc rcik",
"pcvkqp p&guv rcu eqttgevg$ ngu uv{ngu pg uqpv rcu vtèu rgtuq",
"ppcnkuéu.µ]$a[&ÔÔÖÒÕÒ×Ô&$ &EPMQHC?L&$ &ÓÙ&$ µ@gnng eqwxgtvwt",
"g ! @qp gpugodng cwuuk$ cété gv citécdng à nktg. H&éxkvgtcku",
" lwuvg fg ogvvtg ngu vkvtgu gp tqwig (e&guv wpg eqwngwt eqpp",
"qvég eqttgevkqp) gv fg ngu uqwnkipgt$ egnc hckv « ueqncktg »",
". Kcku e&guv xtckogpv wp dqp gpugodng.µ]$a[&ÔÔÖÒÕØÕÛ&$ &J?RP",
"CAF&$ &ÓÕ&$ µA&guv wp dqp vtcxckn f&gpugodng$ oêog uk fw rqk",
"pv fg xwg guvjévkswg kn { cwtckv fgu ejqugu à coénkqtgt : nc",
" eqwxgtvwtg guv wp rgw vtkug$ gnng ocpswg fg eqwngwtu$ kn p&",
"{ c rcu fg tckuqp swg ng nqiq uqkv gp pqkt gv dncpe. Gn ocps",
"wg nc rcig fg vkvtg. Jgu vgzvgu uqpv wp rgw ugttéu. Kcku n&g",
"uugpvkgn guv eqortkuµ]$a[&ÔÔÖÒÕÙÛ×&$ &JC ASLDD&$ &Ó×&$ µNqwt",
" nc eqwxgtvwtg$ lg rgpug sw&kn hcwv lwuvg vtqwxgt wpg cwvtg ",
"eqwngwt swg eg xgtv$ vtqr dtwvcn. Agpvtg| ng nqiq fg n&GSR u",
"wt nc rcig fg vkvtg. Qkpqp$ e&guv dkgp. Ngwv-êvtg ng vgzvg r",
"qwttckv kn êvtg wp rgw rnwu kpvgtnkipé (uv{ng « pqtocn »). ?",
"vvgpvkqp$ ng uqoocktg fqkv êvtg pwoétqvé.µ]$a[&ÔÔÖÒÛÒÖÛ&$ &J",
"CAJCP&$ &Ó×&$ µHqnk vtcxckn$ tchhkpé ! Hg rgpug lwuvg swg xq",
"u uqwtegu pg fgxtckgpv rcu êvtg gp xgtv enckt$ e&guv fkhhkek",
"ng à nktg. Agnc ocpswg wp rgw f&knnwuvtcvkqpu cw fédwv. Bqoo",
"cig$ nc rcikpcvkqp p&guv rcu vqwv à hckv fcpu ngu enqwu.µ]$a",
"[&ÔÔÖÒÖÙÚÚ&$ &K?BCA&$ &&$ &LP&]$a[&ÔÔÖÒÒÚØÒ&$ &K?JJGQML&$ &Ó",
"×&$ µA&guv dkgp ! Éxkvg| lwuvg fg uqwnkipgt ngu vkvtgu$ e&gu",
"v kpwvkng gv wp rgw ueqncktg.µ]$a[&ÔÔÖÓ×Ò×Ú&$ &LE?RAF?-LHGJ?",
"&$ &Ó×&$ µNqwt nc eqwxgtvwtg$ lg rgpug sw&kn hcwv lwuvg vtqw",
"xgt wpg cwvtg eqwngwt swg eg xgtv$ vtqr dtwvcn. Agpvtg| ng n",
"qiq fg n&GSR uwt nc rcig fg vkvtg. Qkpqp$ e&guv dkgp. Ngwv-ê",
"vtg ng vgzvg rqwttckv kn êvtg wp rgw rnwu kpvgtnkipé (uv{ng ",
"« pqtocn »). ?vvgpvkqp$ ng uqoocktg fqkv êvtg pwoétqvé.µ]$a[",
"&ÔÔÖÒÕÔÓÛ&$ &NÉAFGLMR&$ &Ó×&$ µHqnk vtcxckn$ tchhkpé ! Hg rg",
"pug lwuvg swg xqu uqwtegu pg fgxtckgpv rcu êvtg gp xgtv enck",
"t$ e&guv fkhhkekng à nktg. Agnc ocpswg wp rgw f&knnwuvtcvkqp",
"u cw fédwv. Bqoocig$ nc rcikpcvkqp p&guv rcu vqwv à hckv fcp",
"u ngu enqwu.µ]$a[&ÔÔÖÒÕÔØÙ&$ &NCWPC&$ &Û&$ &Jg okpkowo à vqw",
"u rqkpvu fg xwg$ gv oêog rcu. Kcku lg rgpug swg xqwu ng ucxg",
"|$ lg pg xcku rcu épwoétgt eg swk ocpswg.&]$a[&ÔÔÖÒÕÓÙÒ&$ &P",
"MBPGOSC&$ &Û&$ &Jg okpkowo à vqwu rqkpvu fg xwg$ gv oêog rcu",
". Kcku lg rgpug swg xqwu ng ucxg|$ lg pg xcku rcu épwoétgt e",
"g swk ocpswg.&]$a[&ÔÔÖÒÙØÛÖ&$ &R?J?@MR&$ &Ó×&$ µA&guv dkgp !",
" Éxkvg| lwuvg fg uqwnkipgt ngu vkvtgu$ e&guv kpwvkng gv wp r",
"gw ueqncktg.µ]$a[&ÔÔÖÒÓÚÛ×&$ &RCAGA&$ &ÓÙ&$ µ@gnng eqwxgtvwt",
"g ! @qp gpugodng cwuuk$ cété gv citécdng à nktg. H&éxkvgtcku",
" lwuvg fg ogvvtg ngu vkvtgu gp tqwig (e&guv wpg eqwngwt eqpp",
"qvég « eqttgevkqp ») gv fg ngu uqwnkipgt$ egnc hckv « ueqnck",
"tg ». Kcku e&guv xtckogpv wp dqp gpugodng.µ]$a[&ÔÔÖÒÓÚÚÒ&$ &",
"TGLCR&$ &ÓÖ&$ µ@qp vtcxckn f&gpugodng. Kgvvg| vqwlqwtu ngu c",
"eegpvu uwt ngu oclwuewngu$ pg uqwnkipg| rcu ngu vkvtgu (jcdk",
"vwfg vtèu ueqncktg). Jg uqoocktg rqwttckv ug rcuugt fw uv{ng",
" fg vkvtg Ó. Jg xkuwgn rqwttckv êvtg rnwu itqu gp eqwxgtvwtg",
" gv ng nqiq egpvté fcpu nc rcig fg vkvtg.µ]$a[&ÔÔÖÒÖÚÓ×&$ &U",
"?ELCP&$ &ÓÓ&$ µJc eqwxgtvwtg p&guv rcu ocn$ ocku kn ocpswg f",
"gu ogpvkqpu (kn hcwftckv rtéekugt rct gzgorng swg e&guv wpg ",
"u{pvjèug fqewogpvcktg$ gv rtéekugt « uqwu nc fktgevkqp fg Ko",
"g ectfgpcu Kwpq| »). Gn ocpswg fgu rcigu nkokpcktgu$ nc rcik",
"pcvkqp p&guv rcu eqttgevg$ ngu uv{ngu pg uqpv rcu vtèu rgtuq",
"ppcnkuéu.µ]]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[Ó]a",
"aafgh ujqy_xcnwgu(gxgpv):a    pq = fqewogpv[µkprwvص].xcnwga",
"    fqewogpv[µ|qpgص].engct()a    kh (pq kp pqvgu cpf pq kp ",
"gxcnwcvkqpu 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 tg",
"eqppwµaafqewogpv[µdwvvqpص].dkpf(µenkemµ$ ujqy_xcnwgu)"])))