import string

englishWords = "the of to in and a for was is that on at he with by be it an as his".upper().split()
frequency = "e t a o i n s r h l d c u m f p g w y b v k x j q z".upper().split()
abc = list(string.ascii_uppercase)
encrypt1 = "vkwl dy dro cvkeqrdob  li bykvn nkrv   dro byyw gkc gkbw kxn mvokx dro mebdksxc nbkgx dro dgy dklvo vkwzc kvsqrd  robc kxn dro yxo li dro owzdi mrksb yzzycsdo yx dro csnolykbn lorsxn rob dgy dkvv qvkccoc cynk gkdob grscuoi  pbocr smo meloc sx dro drobwyc lemuod  wkbi wkvyxoi gkc gksdsxq pyb rob reclkxn dy mywo rsw pbyw gybu  xyg kxn kqksx cro gyevn qvkxmo ez kd dro mvymu led gsdryed kxhsodi wobovi dy zvokco robcovp gsdr dro dryeqrd drkd okmr wsxedo qyxo li wkno sd xokbob dro dswo grox ro gyevn mywo  drobo gkc k cvyg cwsvsxq ksb klyed rob kxn klyed ofobidrsxq cro nsn  dro nbyz yp k rokn kc cro loxd yfob rob cogsxq gkc mebsyecvi dbkxaesv  rob cusx  pyb drsc gkc rob cshdr wyxdr gsdr mrsvn  rkn kmaesbon k gyxnobpev dbkxcvemoxd aekvsdi dro wyedr gkc cypd kxn dro oioc gsdr drosb xog zvkmsn vyyu coowon vkbqob nkbuob drkx lopybo grox dro mvymu cksn dox wsxedoc dy psfo cro loqkx dy vscdox kxn k pog wywoxdc vkdob zexmdekvvi kc kvgkic cro rokbn dro dsboc yx dro qbkfov yedcsno kxn dro mkb nyyb cvkwwsxq dro pyydcdozc zkccsxq dro gsxnyg dro uoi debxsxq sx dro vymu  cro vksn kcsno rob cogsxq cdyyn ez kxn goxd pybgkbn dy uscc rsw kc ro mkwo sx  revvy nkbvsxq cro cksn  revvy nkbvsxq ro kxcgobon  cro dyyu rsc mykd kxn rexq sd sx dro mvycob  drox cro gkvuon yfob kxn wkno dro nbsxuc k cdbyxqscr yxo pyb rsw k goku yxo pyb robcovp kxn cyyx cro gkc lkmu kqksx sx rob mrksb gsdr dro cogsxq kxn ro sx dro ydrob yzzycsdo ryvnsxq dro dkvv qvkcc gsdr lydr rkxnc bymusxq sd cy dro smo meloc dsxuvon kqksxcd dro csno  pyb rob drsc gkc kvgkic k lvsccpev dswo yp nki  cro uxog ro nsnxd gkxd dy czoku wemr exdsv dro psbcd nbsxu gkc psxscron kxn cro yx rob csno gkc myxdoxd dy csd aesodvi oxtyisxq rsc mywzkxi kpdob dro vyxq ryebc kvyxo sx dro ryeco  cro vyfon dy vehebskdo sx dro zbocoxmo yp drsc wkx kxn dy poov  kvwycd kc k cexlkdrob poovc dro cex  drkd gkbw wkvo qvyg drkd mkwo yed yp rsw dy rob grox droi gobo kvyxo dyqodrob  cro vyfon rsw pyb dro gki ro ckd vyycovi sx k mrksb pyb dro gki ro mkwo sx k nyyb yb wyfon cvygvi kmbycc dro byyw gsdr vyxq cdbsnoc  cro vyfon sxdoxd pkb vyyu sx rsc oioc grox droi bocdon sx rob dro pexxi crkzo yp dro wyedr kxn oczomskvvi dro gki ro bowksxon csvoxd klyed rsc dsbonxocc csddsxq cdsvv gsdr rswcovp exdsv dro grscuoi rkn dkuox cywo yp sd kgki  dsbon nkbvsxq  ioc ro cksn  sw dsbon  kxn kc ro czyuo ro nsn kx execekv drsxq  ro vspdon rsc qvkcc kxn nbksxon sd sx yxo cgkvvyg kvdryeqr drobo gkc cdsvv rkvp yp sd kd vokcd rkvp yp sd vopd cro gkcxd bokvvi gkdmrsxq rsw led cro uxog grkd ro rkn nyxo lomkeco cro rokbn dro smo meloc pkvvsxq lkmu kqksxcd dro lyddyw yp dro owzdi qvkcc grox ro vygobon rsc kbw  ro zkecon k wywoxd vokxsxq pybgkbn sx dro mrksb drox ro qyd ez kxn goxd cvygvi yfob dy podmr rswcovp kxydrob  svv qod sd cro mbson tewzsxq ez  csd nygx ro cksn  grox ro mkwo lkmu cro xydsmon drkd dro xog nbsxu gkc nkbu kwlob gsdr dro aekxdsdi yp grscuoi sx sd  nkbvsxq crkvv s qod iyeb cvszzobc  xy  cro gkdmron rsw kc ro loqkx dy csz dro nkbu iovvyg nbsxu kxn cro myevn coo vsddvo ysvi cgsbvc sx dro vsaesn lomkeco sd gkc cy cdbyxq  s drsxu sdc k crkwo cro cksn drkd grox k zyvsmowkx qodc dy lo kc coxsyb kc iye droi uooz rsw gkvusxq klyed yx rsc pood kvv nki vyxq  ro nsnxd kxcgob cy cro loxd rob rokn kqksx kxn goxd yx gsdr rob cogsxq lod okmr dswo ro vspdon dro nbsxu dy rsc vszc cro rokbn dro smo meloc mvsxusxq kqksxcd dro csno yp dro qvkcc  nkbvsxq cro cksn  gyevn iye vsuo wo dy qod iye cywo mrooco  s rkfoxd wkno kxi cezzob lomkeco sdc drebcnki  xy ro cksn  sp iyebo dyy dsbon dy okd yed cro goxd yx sdc cdsvv xyd dyy vkdo  droboc zvoxdi yp wokd kxn cdepp sx dro pboojob kxn iye mkx rkfo sd bsqrd robo kxn xyd ofox wyfo yed yp dro mrksb  rob oioc gksdon yx rsw pyb kx kxcgob k cwsvo k vsddvo xyn led ro wkno xy csqx  kxigki cro goxd yx svv qod iye cywo mrooco kxn mbkmuobc psbcd  s nyxd gkxd sd ro cksn  cro wyfon exokcsvi sx rob mrksb dro vkbqo oioc cdsvv gkdmrsxq rsc pkmo  led iye wecd okd  svv psh sd kxigki kxn drox iye mkx rkfo sd yb xyd kc iye vsuo  cro cdyyn ez kxn zvkmon rob cogsxq yx dro dklvo li dro vkwz  csd nygx ro cksn  tecd pyb k wsxedo csd nygx  sd gkcxd dsvv drox drkd cro loqkx dy qod pbsqrdoxon  qy yx ro cksn  csd nygx  cro vygobon robcovp lkmu cvygvi sxdy dro mrksb gkdmrsxq rsw kvv dro dswo gsdr dryco vkbqo logsvnobon oioc  ro rkn psxscron dro comyxn nbsxu kxn gkc cdkbsxq nygx sxdy dro qvkcc pbygxsxq  vscdox ro cksn  sfo qyd cywodrsxq dy dovv iye  grkd sc sd nkbvsxq  grkdc dro wkddob  ro rkn xyg lomywo klcyvedovi wydsyxvocc kxn ro uozd rsc rokn nygx cy drkd dro vsqrd pbyw dro vkwz locsno rsw povv kmbycc dro ezzob zkbd yp rsc pkmo vokfsxq dro mrsx kxn wyedr sx crknyg  cro xydsmon drobo gkc k vsddvo wecmvo wyfsxq xokb dro mybxob yp rsc vopd oio  drsc sc qysxq dy lo k lsd yp k crymu dy iye sw kpbksn ro cksn  led sfo dryeqrd klyed sd k qyyn nokv kxn sfo nomsnon dro yxvi drsxq dy ny sc dovv iye bsqrd kgki  s ryzo iye gyxd lvkwo wo dyy wemr  kxn ro dyvn rob  sd nsnxd dkuo vyxq pyeb yb psfo wsxedoc kd wycd kxn cro cki fobi cdsvv drbyeqr sd kvv gkdmrsxq rsw gsdr k usxn yp nkjon rybbyb kc ro goxd pebdrob kxn pebdrob kgki pbyw rob gsdr okmr gybn  cy drobo sd sc ro knnon  kxn s uxyg sdc usxn yp k lkn dswo dy lo dovvsxq iye lod drobo cswzvi gkcxd kxi ydrob gki  yp myebco svv qsfo iye wyxoi kxn coo iyebo vyyuon kpdob  led drobo xoonxd bokvvi lo kxi pecc  s ryzo xyd kxigki  sd gyevnxd lo fobi qyyn pyb wi tyl  rob psbcd sxcdsxmd gkc xyd dy lovsofo kxi yp sd dy botomd sd kvv  sd ymmebbon dy rob drkd zobrkzc ro rknxd ofox czyuox drkd cro robcovp rkn swkqsxon dro gryvo drsxq  wkilo sp cro goxd klyed rob lecsxocc kxn kmdon kc dryeqr cro rknxd loox vscdoxsxq drox vkdob grox cro cybd yp gyuo ez kqksx cro wsqrd psxn xyxo yp sd rkn ofob rkzzoxon  svv qod dro cezzob cro wkxkqon dy grsczob kxn drsc dswo ro nsnxd cdyz rob  grox cro gkvuon kmbycc dro byyw cro myevnxd poov rob pood dyemrsxq dro pvyyb  cro myevnxd poov kxidrsxq kd kvv   ohmozd k cvsqrd xkecok kxn k nocsbo dy fywsd  ofobidrsxq gkc kedywkdsm xyg  nygx dro cdozc dy dro movvkb dro vsqrd cgsdmr dro nooz pboojo dro rkxn sxcsno dro mklsxod dkusxq ryvn yp dro psbcd yltomd sd wod  cro vspdon sd yed kxn vyyuon kd sd  sd gkc gbkzzon sx zkzob cy cro dyyu ypp dro zkzob kxn vyyuon kd sd kqksx  k voq yp vkwl  kvv bsqrd drox droi gyevn rkfo vkwl pyb cezzob  cro mkbbson sd ezcdksbc ryvnsxq dro drsx lyxo  oxn yp sd gsdr lydr rob rkxnc kxn kc cro goxd drbyeqr dro vsfsxq  byyw cro ckg rsw cdkxnsxq yfob li dro gsxnyg gsdr rsc lkmu dy rob kxn cro cdyzzon  pyb qync ckuo ro cksn rokbsxq rob led xyd debxsxq byexn  nyxd wkuo cezzob pyb wo  sw qysxq yed  kd drkd zysxd wkbi wkvyxoi cswzvi gkvuon ez lorsxn rsw kxn gsdryed kxi zkeco cro cgexq dro lsq pbyjox voq yp vkwl rsqr sx dro ksb kxn lbyeqrd sd nygx kc rkbn kc cro myevn yx dro lkmu yp rsc rokn  cro wsqrd tecd kc govv rkfo rsd rsw gsdr k cdoov mvel  cro cdozzon lkmu k zkmo gksdsxq kxn dro pexxi drsxq gkc drkd ro bowksxon cdkxnsxq drobo pyb kd vokcd pyeb yb psfo comyxnc qoxdvi cgkisxq  drox ro mbkcron dy dro mkbzod  dro fsyvoxmo yp dro mbkcr dro xysco dro cwkvv dklvo yfobdebxsxq rovzon lbsxq rob yed yp ro crymu  cro mkwo yed cvygvi poovsxq myvn kxn cebzbscon kxn cro cdyyn pyb k grsvo lvsxusxq kd dro lyni cdsvv ryvnsxq dro bsnsmevyec zsomo yp wokd dsqrd gsdr lydr rkxnc  kvv bsqrd cro dyvn robcovp  cy sfo usvvon rsw  sd gkc ohdbkybnsxkbi xyg ryg mvokb rob wsxn lomkwo kvv yp k cennox  cro loqkx drsxusxq fobi pkcd  kc dro gspo yp k nodomdsfo cro uxog aesdo govv grkd dro zoxkvdi gyevn lo  drkd gkc psxo  sd wkno xy nsppoboxmo dy rob  sx pkmd sd gyevn lo k bovsop  yx dro ydrob rkxn grkd klyed dro mrsvn  grkd gobo dro vkgc klyed webnobobc gsdr exlybx mrsvnbox  nsn droi usvv drox lydr  wydrob kxn mrsvn  yb nsn droi gksd exdsv dro doxdr wyxdr  grkd nsn droi ny  wkbi wkvyxoi nsnxd uxyg  kxn cro mobdksxvi gkcxd zbozkbon dy dkuo k mrkxmo  cro mkbbson dro wokd sxdy dro usdmrox zvkmon sd sx k zkx debxon dro yfox yx rsqr kxn cryfon d sxcsno  drox cro gkcron rob rkxnc kxn bkx ezcdksbc dy dro lonbyyw  cro ckd nygx lopybo dro wsbbyb dsnson rob rksb dyemron ez rob vyzc kxn pkmo  cro dbson k cwsvo  sd mkwo yed bkdrob zomevskb  cro dbson kqksx  revvy ckw cro cksn lbsqrdvi kvyen  dro fysmo cyexnon zomevskb dyy  s gkxd cywo zydkdyoc zvokco ckw  ioc kxn s drsxu k mkx yp zokc  drkd gkc loddob  lydr dro cwsvo kxn dro fysmo gobo mywsxq yed loddob xyg  cro borokbcon sd cofobkv dswoc wybo  drox cro bkx nygxcdksbc dyyu rob mykd goxd yed dro lkmu nyyb nygx dro qkbnox sxdy dro cdbood  sd gkcxd csh ymvymu iod kxn dro vsqrdc gobo cdsvv yx sx dro qbymobi cryz  revvy ckw cro cksn lbsqrdvi cwsvsxq kd dro wkx lorsxn dro myexdob  gri qyyn ofoxsxq wbc wkvyxoi  rygbo iye  s gkxd cywo zydkdyoc zvokco ckw  ioc kxn s drsxu k mkx yp zokc  dro wkx debxon kxn bokmron ez lorsxn rsw yx dro crovp pyb dro zokc  zkdbsmuc nomsnon roc dsbon kxn nyocxd gkxd dy okd yed dyxsqrd cro dyvn rsw  go ecekvvi qy yed drebcnkic iye uxyg kxn xyg roc mkeqrd wo gsdryed kxi foqodklvoc sx dro ryeco  drox ryg klyed wokd wbc wkvyxoi  xy sfo qyd wokd drkxuc  s qyd k xsmo voq yp vkwl pbyw dro pboojob  yr  s nyxd uxyg wemr vsuo myyusxq sd pbyjox ckw led sw dkusxq k mrkxmo yx sd drsc dswo  iye drsxu sdvv lo kvv bsqrd  zobcyxkvvi dro qbymob cksn s nyxd lovsofo sd wkuoc kxi nsppoboxmo  iye gkxd droco snkry zydkdyoc  yr ioc drkdvv lo psxo  dgy yp dryco  kxidrsxq ovco dro qbymob mymuon rsc rokn yx yxo csno vyyusxq kd rob zvokckxdvi  ryg klyed kpdobgkbnc  grkd iye qysxq dy qsfo rsw pyb kpdobgkbnc  govv  grkd gyevn iye ceqqocd ckw  dro wkx qvkxmon kbyexn rsc cryz  ryg klyed k xsmo lsq cvsmo yp mroocomkuo  s uxyg ro vsuoc drkd  zobpomd cro cksn  ro vyfoc sd  kxn grox sd gkc kvv gbkzzon kxn cro rkn zksn cro zed yx rob lbsqrdocd cwsvo kxn cksn drkxu iye ckw  qyynxsqrd  qyynxsqrd wbc wkvyxoi  kxn drkxu iye  kxn xyg cro dyvn robcovp kc cro rebbson lkmu kvv cro gkc nysxq xyg cro gkc bodebxsxq rywo dy rob reclkxn kxn ro gkc gksdsxq pyb rsc cezzob kxn cro wecd myyu sd qyyn kxn wkuo sd kc dkcdi kc zyccslvo lomkeco dro zyyb wkx gkc dsbon kxn sp grox cro oxdobon dro ryeco cro rkzzoxon dy psxn kxidrsxq execekv yb dbkqsm yb dobbslvo drox xkdebkvvi sd gyevn lo k crymu kxn cron lomywo pbkxdsm gsdr qbsop kxn rybbyb  wsxn iye cro gkcxd ohzomdsxq dy psxn kxidrsxq  cro gkc tecd qysxq rywo gsdr dro foqodklvoc wbc zkdbsmu wkvyxoi qysxq rywo gsdr dro foqodklvoc yx drebcnki ofoxsxq dy myyu cezzob pyb rob reclkxn  drkdc dro gki cro dyvn robcovp  ny ofobidrsxq bsqrd kxn xkdebkv  uooz drsxqc klcyvedovi xkdebkv kxn drobovv lo xy xoon pyb kxi kmdsxq kd kvv  drobopybo grox cro oxdobon dro usdmrox li dro lkmu nyyb cro gkc rewwsxq k vsddvo dexo dy robcovp kxn cwsvsxq  zkdbsmu cro mkvvon  ryg kbo iye nkbvsxq  cro zed dro zkbmov nygx yx dro dklvo kxn goxd drbyeqr sxdy dro vsfsxq byyw kxn grox cro ckg rsw visxq drobo yx dro pvyyb gsdr rsc voqc nyelvon ez kxn yxo kbw dgscdon lkmu exnobxokdr rsc lyni sd bokvvi gkc bkdrob k crymu  kvv dro yvn vyfo kxn vyxqsxq pyb rsw govvon ez sxcsno rob kxn cro bkx yfob dy rsw uxovd nygx locsno rsw kxn loqkx dy mbi rob rokbd yed  sd gkc okci  xy kmdsxq gkc xomocckbi  k pog wsxedoc vkdob cro qyd ez kxn goxd dy dro zryxo  cro uxyg dro xewlob yp dro zyvsmo cdkdsyx kxn grox dro wkx kd dro ydrob oxn kxcgobon cro mbson dy rsw aesmu  mywo aesmu  zkdbsmuc nokn  gryc czokusxq  wbc wkvyxoi  wbc zkdbsmu wkvyxoi  iye wokx zkdbsmu wkvyxoic nokn  s drsxu cy cro cyllon  roc visxq yx dro pvyyb kxn s drsxu roc nokn  lo bsqrd yfob dro wkx cksn  dro mkb mkwo fobi aesmuvi kxn grox cro yzoxon dro pbyxd nyyb dgy zyvsmowkx gkvuon sx  cro uxyg drow lydr  cro uxyg xokbvi kvv dro wkx kd drkd zbomsxmd  kxn cro povv bsqrd sxdy k mrksb drox goxd yfob dy tysx dro ydrob yxo gry gkc mkvvon ywkvvoi uxoovsxq li dro lyni  sc ro nokn cro mbson  sw kpbksn ro sc  grkd rkzzoxon  lbsopvi cro dyvn rob cdybi klyed qysxq yed dy dro qbymob kxn mywsxq lkmu dy psxn rsw yx dro pvyyb  grsvo cro gkc dkvusxq mbisxq kxn dkvusxq xyyxkx nscmyfobon k cwkvv zkdmr yp myxqokvon lvyyn yx dro nokn wkxc rokn  ro crygon sd dy ywkvvoi gry qyd ez kd yxmo kxn rebbson dy dro zryxo  cyyx ydrob wox loqkx dy mywo sxdy dro ryeco  psbcd k nymdyb drox dgy nodomdsfoc yxo yp gryw cro uxyg li xkwo  vkdob k zyvsmo zrydyqbkzrob kbbsfon kxn dyyu zsmdeboc kxn k wkx gry uxyg klyed psxqobzbsxdc  drobo gkc k qbokd nokv yp grsczobsxq kxn weddobsxq locsno dro mybzco kxn dro nodomdsfoc uozd kcusxq rob k vyd yp aeocdsyxc  led droi kvgkic dbokdon rob usxnvi  cro dyvn rob cdybi kqksx drsc dswo bsqrd pbyw dro loqsxxsxq grox zkdbsmu rkn mywo sx kxn cro gkc cogsxq kxn ro gkc dsbon cy dsbon ro rknxd gkxdon dy qy yed pyb cezzob  cro dyvn ryg cron zed dro wokd sx dro yfox  sdc drobo xyg myyusxq   kxn ryg cron cvyzzon yed dy dro qbymob pyb foqodklvoc kxn mywo lkmu dy psxn rsw visxq yx dro pvyyb  grsmr qbymob yxo yp dro nodomdsfoc kcuon  cro dyvn rsw kxn ro debxon kxn grsczobon cywodrsxq dy dro ydrob nodomdsfo gry swwonskdovi goxd yedcsno sxdy dro cdbood  sx pspdoox wsxedoc ro gkc lkmu gsdr k zkqo yp xydoc kxn drobo gkc wybo grsczobsxq kxn drbyeqr rob cyllsxq cro rokbn k pog yp dro grsczobon zrbkcoc  kmdon aesdo xybwkvfobi mroobpevgkxdon dy qsfo rsw k qyyn cezzob zokcmroocomkuoswzyccslvo drkd cro  kpdob k grsvo dro zrydyqbkzrob kxn dro nymdyb nozkbdon kxn dgy ydrob wox mkwo sx kxn dyyu dro mybzco kgki yx k cdbodmrob  drox dro psxqobzbsxd wkx goxd kgki  dro dgy nodomdsfoc bowksxon kxn cy nsn dro dgy zyvsmowkx  droi gobo ohmozdsyxkvvi xsmo dy rob kxn tkmu xyyxkx kcuon sp cro gyevnxd bkdrob qy cywogrobo ovco dy rob cscdobc ryeco zobrkzc yb dy rsc ygx gspo gry gyevn dkuo mkbo yp rob kxn zed rob ez pyb dro xsqrd  xy cro cksn  cro nsnxd poov cro myevn wyfo ofox k ikbn kd dro wywoxd  gyevn droi wsxn kgpevvi yp cro cdkion tecd grobo cro gkc exdsv cro povd loddob  cro nsnxd poov dyy qyyn kd dro wywoxd cro bokvvi nsnxd  drox rknxd cro loddob vso nygx yx dro lon  tkmu xyyxkx kcuon  xy cro cksn  cron vsuo dy cdki bsqrd grobo cro gkc sx drsc mrksb  k vsddvo vkdob zobrkzc grox cro povd loddob cro gyevn wyfo  cy droi vopd rob drobo grsvo droi goxd klyed drosb lecsxocc cokbmrsxq dro ryeco  ymmkcsyxkvvi yx yp dro nodomdsfoc kcuon rob kxydrob aeocdsyx  cywodswoc tkmu xyyxkx czyuo kd rob qoxdvi kc ro zkccon li  rob reclkxn ro dyvn rob rkn loox usvvon li k lvyg yx dro lkmu yp dro rokn knwsxscdobon gsdr k rokfi lvexd sxcdbewoxd kvwycd mobdksxvi k vkbqo zsomo yp wodkv  droi gobo vyyusxq pyb dro gokzyx  dro webnobob wki rkfo dkuox sd gsdr rsw led yx dro ydrob rkxn ro wki rkfo drbygx sd kgki yb rsnnox sd cywogrobo yx dro zbowscoc  sdc dro yvn cdybi ro cksn  qod dro gokzyx kxn iyefo qyd dro wkx  vkdob yxo yp dro nodomdsfoc mkwo ez kxn ckd locsno rob  nsn cro uxyg ro kcuon yp kxidrsxq sx dro ryeco drkd myevnfo loox econ kc dro gokzyx  gyevn cro wsxn rkfsxq k vyyu kbyexn dy coo sp kxidrsxq gkc wsccsxq  k fobi lsq czkxxob pyb ohkwzvo yb k rokfi wodkv fkco  droi nsnxd rkfo kxi rokfi wodkv fkcoc cro cksn  yb k lsq czkxxob  cro nsnxd drsxu droi rkn k lsq czkxxob  led drobo wsqrd lo cywo drsxqc vsuo drkd sx dro qkbkqo  dro cokbmr goxd yx  cro uxog drkd drobo gobo ydrob zyvsmowox sx dro qkbnox kvv kbyexn dro ryeco  cro myevn rokb drosb pyydcdozc yx dro qbkfov yedcsno kxn cywodswoc cro ckg k pvkcr yp k dybmr drbyeqr k mrsxu sx dro mebdksxc  sd loqkx dy qod vkdo xokbvi xsxo cro xydsmon li dro mvymu yx dro wkxdvo  dro pyeb wox cokbmrsxq dro byywc coowon dy lo qbygsxq gokbi k dbspvo ohkczobkdon  tkmu cro cksn dro xohd dywo cobqokxd xyyxkx goxd li  gyevn iye wsxn qsfsxq wo k nbsxu  cebo svv qsfo iye k nbsxu  iye wokx drsc grscuoi  ioc zvokco  led tecd k cwkvv yxo  sd wsqrd wkuo wo poov loddob  ro rkxnon rob dro qvkcc  gri nyxd iye rkfo yxo iyebcovp cro cksn  iye wecd lo kgpevvi dsbon  zvokco ny  iyefo loox fobi qyyn dy wo  govv ro kxcgobon  sdc xyd cdbsmdvi kvvygon led s wsqrd dkuo tecd k nbyz dy uooz wo qysxq  yxo li yxo dro ydrobc mkwo sx kxn gobo zobceknon dy dkuo k vsddvo xsz yp grscuoi  droi cdyyn kbyexn bkdrob kgugkbnvi gsdr dro nbsxuc sx drosb rkxnc exmywpybdklvo sx rob zbocoxmo dbisxq dy cki myxcyvsxq drsxqc dy rob  cobqokxd xyyxkx gkxnobon sxdy dro usdmrox mywo yed aesmuvi kxn cksn vyyu wbc wkvyxoi  iye uxyg drkd yfox yp iyebc sc cdsvv yx kxn dro wokd cdsvv sxcsno  yr nokb wo cro mbson  cy sd sc  s loddob debx sd ypp pyb iye rknxd s  gsvv iye ny drkd tkmu  drkxu iye cy wemr  grox dro cobqokxd bodebxon dro comyxn dswo cro vyyuon kd rsw gsdr rob vkbqo nkbu dokbpev oioc  tkmu xyyxkx cro cksn  ioc  gyevn iye ny wo k cwkvv pkfy".upper()
encrypt2 = "drobo kbo cdbkxqo drsxqc nyxo sx dro wsnxsqrd cex li dro wox gry wysv pyb qyvn dro kbmdsm dbksvc rkfo drosb combod dkvoc drkd gyevn wkuo iyeb lvyyn bex myvn dro xybdrobx vsqrdc rkfo coox aeoob csqrdc led dro aeoobocd droi ofob nsn coo gkc drkd xsqrd yx dro wkbqo yp vkuo volkbqo s mbowkdon ckw wmqoo  xyg ckw wmqoo gkc pbyw doxxoccoo grobo dro myddyx lvyywc kxn lvygc gri ro vopd rsc rywo sx dro cyedr dy bykw byexn dro zyvo qyn yxvi uxygc ro gkc kvgkic myvn led dro vkxn yp qyvn coowon dy ryvn rsw vsuo k czovv dryeqr ron ypdox cki sx rsc rywovi gki drkd ron cyyxob vsfo sx rovv  yx k mrbscdwkc nki go gobo wecrsxq yeb gki yfob dro nkgcyx dbksv dkvu yp iyeb myvn drbyeqr dro zkbukc pyvn sd cdkllon vsuo k nbsfox xksv sp yeb oioc gon mvyco drox dro vkcroc pbyjo dsvv cywodswoc go myevnxd coo sd gkcxd wemr pex led dro yxvi yxo dy grswzob gkc ckw wmqoo  kxn drkd fobi xsqrd kc go vki zkmuon dsqrd sx yeb byloc loxokdr dro cxyg kxn dro nyqc gobo pon kxn dro cdkbc yobrokn gobo nkxmsxq roov kxn dyo ro debxon dy wo kxn mkz ckic ro svv mkcr sx drsc dbsz s qeocc kxn sp s ny sw kcusxq drkd iye gyxd bopeco wi vkcd boaeocd  govv ro coowon cy vyg drkd s myevnxd cki xy drox ro ckic gsdr k cybd yp wykx sdc dro mebcon myvn kxn sdc qyd bsqrd ryvn dsvv sw mrsvvon mvokx drbyeqr dy dro lyxo iod dksxd losxq nokn  sdc wi kgpev nbokn yp dro smi qbkfo drkd zksxc cy s gkxd iye dy cgokb drkd pyev yb pksb iyevv mbowkdo wi vkcd bowksxc  k zkvc vkcd xoon sc k drsxq dy roon cy s cgybo s gyevn xyd pksv kxn go cdkbdon yx kd dro cdboku yp nkgx led qyn ro vyyuon qrkcdvi zkvo ro mbyemron yx dro cvosqr kxn ro bkfon kvv nki yp rsc rywo sx doxxoccoo kxn lopybo xsqrdpkvv k mybzco gkc kvv drkd gkc vopd yp ckw wmqoo  drobo gkcxd k lbokdr sx drkd vkxn yp nokdr kxn s rebbson rybbybnbsfox gsdr k mybzco rkvp rsn drkd s myevnxd qod bsn lomkeco yp k zbywsco qsfox sd gkc vkcron dy dro cvosqr kxn sd coowon dy cki iye wki dkh iyeb lbkgx kxn lbksxc led iye zbywscon dbeo kxn sdc ez dy iye dy mbowkdo dryco vkcd bowksxc  xyg k zbywsco wkno sc k nold exzksn kxn dro dbksv rkc sdc ygx cdobx myno sx dro nkic dy mywo dryeqr wi vszc gobo newl sx wi rokbd ryg s mebcon drkd vykn sx dro vyxq vyxq xsqrd li dro vyxo psbovsqrd grsvo dro recusoc byexn sx k bsxq rygvon yed drosb gyoc dy dro rywovocc cxygc  y qyn ryg s vykdron dro drsxq  kxn ofobi nki drkd aesod mvki coowon dy rokfi kxn rokfsob qbyg kxn yx s goxd dryeqr dro nyqc gobo czoxd kxn dro qbel gkc qoddsxq vyg dro dbksv gkc lkn kxn s povd rkvp wkn led s cgybo s gyevn xyd qsfo sx kxn sn ypdox csxq dy dro rkdopev drsxq kxn sd rokbuoxon gsdr k qbsx  dsvv s mkwo dy dro wkbqo yp vkuo volkbqo kxn k nobovsmd drobo vki sd gkc tkwwon sx dro smo led s ckg sx k dbsmo sd gkc mkvvon dro kvsmo wki kxn s vyyuon kd sd kxn s dryeqrd k lsd kxn s vyyuon kd wi pbyjox mrew drox robo cksn s gsdr k cennox mbi sc wi mbowkdyboew  cywo zvkxuc s dybo pbyw dro mklsx pvyyb kxn s vsd dro lysvob psbo cywo mykv s pyexn drkd gkc visxq kbyexn kxn s rokzon dro peov rsqrob dro pvkwoc tecd cykbon kxn dro pebxkmo bykboncemr k lvkjo iye covnyw coo drox s lebbygon k ryvo sx dro qvygsxq mykv kxn s cdeppon sx ckw wmqoo  drox s wkno k rsuo pyb s nsnxd vsuo dy rokb rsw csjjvo cy kxn dro rokfoxc cmygvon kxn dro recusoc rygvon kxn dro gsxn loqkx dy lvyg sd gkc smi myvn led dro ryd cgokd byvvon nygx wi mroouc kxn s nyxd uxyg gri kxn dro qbokci cwyuo sx kx sxui mvyku goxd cdbokusxq nygx dro cui  s ny xyd uxyg ryg vyxq sx dro cxyg s gbocdvon gsdr qbscvi pokb led dro cdkbc mkwo yed kxn droi nkxmon klyed obo kqksx s foxdebon xokb s gkc csmu gsdr nbokn led s lbkfovi cksn svv tecd dkuo k zooz sxcsno s qeocc roc myyuon kxn sdc dswo s vyyuon    drox dro nyyb s yzoxon gsno  kxn drobo ckd ckw vyyusxq myyv kxn mkvw sx dro rokbd yp dro pebxkmo bykb kxn ro gybo k cwsvo iye myevn coo k wsvo kxn ro cksn zvokco mvyco drkd nyyb sdc psxo sx robo led s qbokdvi pokb iyevv vod sx dro myvn kxn cdybw  csxmo s vopd zvewdboo nygx sx doxxoccoo sdc dro psbcd dswo sfo loox gkbw  drobo kbo cdbkxqo drsxqc nyxo sx dro wsnxsqrd cex     li dro wox gry wysv pyb qyvn  dro kbmdsm dbksvc rkfo drosb combod dkvoc     drkd gyev".upper()
encrypt3 = 'Vs lbh hfr "thrff" nf gur xrl, gur nytbevguz gevrf gb svaq gur evtug xrl naq qrpelcgf gur fgevat ol thrffvat. V nyfb jebgr n fznyy negvpyr (jvgu fbhepr choyvpngvba) nobhg svaqvat gur evtug xrl va na haxabja pbagrkg bs na rapelcgrq grkg. Vs lbh jnag gb xabj zber, V uvtuyl erpbzzrag guvf obbx.'.upper()

# returns true if given char is in the alphabet
def isLetter(char):
	char = char.upper()
	for let in abc:
		if char == let:
			return True
	return False

# returns given string without spaces or special characters (not alphabetical)
def strip(en):
	out = ''
	en = en.upper()
	for char in en:
		if isLetter(char):
			out += char
	return out

# gets letter index in regular abc (0 to 25 inclusive)
def getLetIndex(let):
	for i in range(0,26):
		if let == abc[i]:
			return i

# sorts given dictionary, outputs keys/values from highest to lowest
def sortDict(d):
	key = []
	value = []
	while len(d) > 0:
		largest = 0
		largeKey = ''
		for tempkey, tempvalue in d.iteritems():
			if tempvalue > largest:
				largest = tempvalue
				largeKey = tempkey
		key.append(largeKey)
		value.append(largest)
		del d[largeKey]
	return key, value

# given string or list, outputs
def getDistr(st):
	if type(st) is str:
		words = ''.join(strip(st).split(' '))
	elif type(st) is list:
		words = st
	else:
		raise ValueError("Wrong input in getDistr!")
	chars = {}
	for char in words:
		if chars.has_key(char):
			chars[char] += 1
		else:
			chars[char] = 1
	return sortDict(chars)

def getCipherDict(shift):
	d = {}
	abc = list(string.ascii_uppercase)
	crypt = list(abc[shift:26] + abc[0:shift])
	for i in range(0,26):
		d[abc[i]] = crypt[i]
	return d

# input end (input), key (letter distr), and number of shifts looked at (default is all)
def decrypt(end, key, number = 26):
	out = []
	end = strip(end)
	shifts = getShifts(key)[0:number]
	for shift in shifts:
		d = getCipherDict(shift)
		en = end.split()
		st = ""
		for word in en:
			for let in word:
				st += d[let]
			st += " "
		out.append(st)
	return out

# input: key is list of most common letters in order (of encrypted words)
# output: a list of shifts
def getShifts(key):
	shifts = []
	for i in range(0, len(key)):
		abcIndex = getLetIndex(frequency[i])
		cipherIndex = getLetIndex(key[i])
		shift = abs(cipherIndex - abcIndex)
		shifts.append(shift)
	return shifts

# input sentence
# if has 5 or more words from top list
def hasWords(en, limit = 5):
	d = {}
	for word in englishWords:
		for w in en.split():
			word = word.upper()
			if w == word:
				if d.has_key(w):
					d[w] += 1
				else:
					d[w] = 1
	if len(d) > limit:
		return True
	else:
		return False

def getBestAnswer(decrypted):
	out = []
	for t in decrypted:
		if hasWords(t):
			out.append(t)
	if out == []:
		for t in decrypted:
			if hasWords(t, 2):
				out.append(t)
	return out

inpu = encrypt3
key1, value1 = getDistr(inpu)
decrypted = decrypt(inpu, key1)
print "The answer is: ", getBestAnswer(decrypted)