undef p;X=[];class String def-@;replace ?-+dup end;def-a;X.reject!{|x|x.__id__==__id__};a.replace(self+?-+a) end end;at_exit{eval C=
(Zlib.inflate (X*?-).tr(?-,'').tr('q-z','0-9').to_i(26).digits(256).pack'C*')};def method_missing n;(X<<n.to_s)[-1]end;require'zlib'
gmlztzdculbtzgtjfetuh---k--htf----d-----------------------------------------------------g-b-----s--t-g--------jmuwescmgchftikfjafccs
ivchcveidpvxdabnvwyga-f--v-------xf----------------------------------------------------q-v---l-------q---------liiNeawriayymwooxgxqw
rfosepqsmojseyezmwbhi--------------ew--------------------------------------------------m---k-r-----------vwu--hiotltdmczwyjmlvbyfqwq
uvvykqdjednoqgtcmtfbzs---------f----o--------------------------------------------------t--a------m----x---f-----dldzsakyofetfozfpmrq
geusutariiiNiulkjbwlm-----d------------------------------------------------------------j---------o---------x--j-uitzrgwpupwhvendhyno
uubvnssiywkklwwdufhhi-rw----k---v-------------------------------------------------------sty-----yg---l---c-v----wkffpskpumolqmkeryzg
zrxdaiposwybbzgxdnegh-----g-----ma--n---------------------------------------------------------j----n--b-n-------yqavmscswdogpcgopygt
axiqfswlhzeamvymdnteo---q-q-w--------------------------fhrmj-----------------hkou-----------f-----d----u-o------evcuxxegekfgivzzujan
nslioftsvqvtkeigvfgwr-------------lyco-----------------igyvg-----------------okuk---------m--b-u--d--y------s---dadjrlykfhtermzfyktu
btoxzfpPicxxfligbivvf--------h----yrat---------------------------------------vjwd---------------------d-ki--o--tyqosehopkwttigwwfskp
komzvnyrvkjcjwbmdwdkp----------vxphiNdtawn--xms-saketo--jnld----ezulntdaz----nzna-----vhjwt------h----x--x--o--saxxsrkgktqotaluylbkk
sclegratyaarmgmepheml----------hwgglhlrfcx--znvmpfsgjx-onhju---gtxsmzqprlt---mjzy---frhdk-------------v---mj----dzjujmbgldfwoybgicwu
tfhgnhlzxlwtdtkgzlaca-------------gmex------arlm--------rvmh-ajtgf-----pqal--wcux-zatyi-------------------------xnluwybcugjclmablshn
tnjohqtqzivgmyutrssil-------------lcwq------jrf--------gcaii-maie------------vvnfjfqwo--------------------------filivosyhkxcvuwdibwj
tyxjiopiFqypvwdzoatuq-------------tdln------cnx---------ffuf-ajvq------------tyyypglpzmj------------------------vtqzwewqdsijrbymvpwn
niNffphoehukpvvmzvhyd-------------ahqd------nfr---------jeqk--toap-----mxhyg-tedv---otrwy-----------------------mjxnrktackwxwiajdnuc
kkxhuwbvibpvgvcampadi-------------ebmencqz--obf--------wfprz---qmrotkijiqv---ggfp-----hlzw----------------------kastwdpxiyftmypuxbtu
xetudmwzpomktgnjkcsyc---------------fwpdx---xb----j-----se-k------tllakc-----gjoo-------we------mic---lktk------ubtnrxvrjzuqlrfrsnmf
okdvfvcdbdqkckjialskk---------------------------v---u-------l----------------------------------z--q--qfg--------aaliNbxbjjpxebboneye
kcbkjmdclwnfawtfnwkeq----------------------------------j---y-------------------------------a---jmbyo-sgef--gf---extljbozuoofgyvsilct
xzoqmsqgzjxxpjqwkjkdd------------------------o--------m-------f---------------------------------n--de-ajz-rzv---fhnpbkrwdxoozpxeaxaf
mbcwxuiqdwcmadheiykaa-----------------------q-f------l---i---------------------------------r----zf---k--y---fi--dcnycheytylcgnioauee
yekiNacriqoevtdjerqbp----------------------------w---yy-----my----------------------------ko--mnbpskr--c-----j--ozyqpbfovhbhyoprzgqr
czwtuopxkdbphocfawvbk--------------------------q-s----j--b---------------------------------hd-xsb----bfiNp--w---fmwuvfambdqvxtzldwmh
xysnyrseydlkjcwfbsjnr-------------------------d-d-------------------------------------------f-enpss---qllpwr----almsdidvjwoigvldfqoa
lrpbixjpofxocxlflscpo------------------------------q-fyu--z-------------------------------------kfd-z---n-------bqxurujnxzurrdgcojks
jetyfdkcekckxbyosbfws-------------wdfhgwuvejjmf-----sxjubpvgcsl-------tnmixpv---------eurabjsdvstfv-------------qcyiqhonwoyixqeonfvp
mopPhywsozohitutgmmrb------------zxwtxe--riedeo---mspgpnv--pimlh------jhtzajk--------qqovvq---ldbrh-------------xtooxpayonpcvvtmvpra
vvuyiunpoeagdzqjecsub------------klrw------snrc---rrct------aajom--------nsyk--------peea-------azq-------------iNjefdkfhnagjicqwmsm
mbwwbfgehhbdmvvlflmee---------------------hkejn---jtbo-------jdtje-------jcei---------afyz-----smtc-------------kksvfjyuaqtohxiohhlz
dvfmfrzcmnsfruhqgjuxz------------------dfxdnlk----kkra-------xmmtf-------jwkw----------rdoozxtcho---------------bbwwferxwnnmdzcniicv
mfneisdlyeqwynldjgonj----------------jgrjvc-------uxga-------ghnpr-------sers--------scbknx----gmjo-------------moedtnlbflhtlkjibrqk
gobwqshnpbdcpjmjaeczr--------------iscsxs---------zfpo-------hhfwy-------qbba-------vhlxc-------ntod------------ndwzdomaptumzejiwqbn
snucynymvfpnadyqkzfcv-------------ggze------------kuvfs-----zuhod--------mylo-------jhwyp-----z-pywd------------dqfmpnevmtqcikbrilto
aotyxkipebdkassogpcbl-----------wgackesmvvsrihhd---orzndjndlzpb----------eobf-------kkayixzyotqfafa-w-----------mjjxoomwdglwvccozzut
rthesuszfwycsqqrtxlot-----------ejcqlhriilqbtrys------lwbkzmvp-----------zzwm-------l--qijwfllndzb-ik-----------mmokqomjepdcotnsiNig
nloryyoswwdmefywnnuhph------------------------------------------------------r--r-nd-----h--x--------------------hlgzeqqslwxgtjgghquf
nssngjtiudsrvfuxjzclhjhj----------------------------------------------------------t----------------k-f-mp-------obhyehqebtpjbkeepqzt
ezogzsimfynqmkteaipejo-g-yser-----------------------------------------------e------h-------------i---y----------qpgcqnltivmmsximbbsy
wtjjolwyoselcumgklqwpldkl-ulm-m---------------------------------------------------------------q---u-f--l--------buixfiitufktsqdtnrei
tgrtitcewseetlpeuuujb-osdokjozc------------------------------------------n---d-----f--------g--------q--g-------jyyqtezuzmcxgpcwuwfx
dpPayqmzxrwhbswwalygfurtkruw-u-k---------------------------------------------d---h------i----------c----i-------ulowcddvjbxthqlxjzbe