def count(e,L):
    """
    gibt die Häufigkeit des Vorkommens des Elements e in der Liste L zurück
    """
    return len([y for y in L if e == y])

def frequency(G):
    """
    gibt eine nach der Haeufigkeit geordnete Liste der in G (string)
    vorkommenden Buchstaben zurueck
    """
    L = list(G)
    n = len(L)
    M = set(L) # Menge der vorkommenden Buchstaben
    return qsort([(b,count(b,L)/n) for b in M],lambda x,y : x[1] > y[1]) 

def vorwaerts(b,v):
    """
    verschiebt den Buchstaben b aus dem großen ABC um den Betrag,
    den der Buchstabe v angibt nach vorne 
    """
    An = ord('A')
    bn = ord(b)-An
    vn = ord(v)-An
    return chr((bn+vn)%26+An)

def rueckwaerts(b,v):
    """
    verschiebt den Buchstaben b aus dem großen ABC um den Betrag,
    den der Buchstabe v angibt zurueck 
    """
    An = ord('A')
    bn = ord(b)-An
    vn = ord(v)-An
    return chr((bn-vn)%26+An)


def genL(L):
    """
    Generator, der immer wieder die Elemente der Liste L zurückgibt
    """
    i = 0
    while True:
        yield L[i]
        if i < len(L)-1:
            i = i + 1
        else:
            i = 0

def verschluessele(t,s):
    """
    verschluesselt den Text t mit dem Schlüsselwort s
    """
    h = zip(t,genL(s))
    return ''.join([vorwaerts(x[0],x[1]) for x in h])

def entschluessele(t,s):
    """
    entschluesselt den Text t mit dem Schlüsselwort s
    """
    h = zip(t,genL(s))
    return ''.join([rueckwaerts(x[0],x[1]) for x in h]) 
       
def autokorr(t,n):
    """
    ermittelt die Anzahl der Uebereinstimmungen des um n verschobenen Textes t
    """
    m = len(t)
    return len([t[i] for i in range(m) if t[i] == t[(i+n)%m]])

def qsort(L,vergleich=lambda x,y : x < y):
    """
    gibt eine mit dem Vergleichsoperator vergleich sortierte Liste L zurueck
    """
    if len(L) <= 1:
        return L
    else:
        kopf = L[0]
        rest = L[1:]
        links  = [x for x in rest if vergleich(x,kopf)]
        rechts = [x for x in rest if not vergleich(x,kopf)]
        return qsort(links,vergleich) + [ kopf ] + qsort(rechts,vergleich)

import math

def keylen(t):
    """
    macht bei einem Vigenere-verschluesselten Text über Autokorrelation
    einen Vorschlag über die Schluessellaenge
    """
    n = len(t)
    dak = sum([autokorr(t,i) for i in range(n)])/n # durchschnittliche AK
    sab = math.sqrt(sum([(autokorr(t,i)-dak)**2 for i in range(n)])/n)
    spitzen = [i for i in range(n) if autokorr(t,i) > dak+0.1*sab]
    lens = len(spitzen)
    diff = qsort([spitzen[i+1]-spitzen[i] for i in range(lens-1)])
    # print(diff) # DEBUG
    return diff[int(3*len(diff)/4)]


def aufteilen(L,n):
    """
    gibt eine Liste von n Teillisten zurück, dabei besteht die erste Liste
    aus den Zeichen mit den Nummern 0,n,2*n,..., die zweite aus den Zeichen
    mit den Nummern 1,n+1,2n+1,... usw.
    """
    return [[L[i] for i in range(len(L)) if i%n == m] for m in range(n)]

def schluessel(k,c):
    """
    ermittelt den Buchstaben v, sodass der Klartextbuchstabe k
    mit einer Verschiebung gemäß v auf den Geheimbuchstaben c
    zu liegen kommt
    """
    An = ord('A')
    kn = ord(k)-An
    cn = ord(c)-An
    return chr((cn-kn)%26+An)



g = "PYIPJMHQYWECJMZQXZZDAGRDTXUZCWPYMSYQHVBWIUICWOBJEFPTNKFLCXKDEYIGSQBIOFPYZXWDTNOAVUVRJUAVXEUMJSGZCEBGYULPVUYJMZDCWDWZUCLWDNZCKFCVCKMHWKFSMYKLFYVBSGZXBMZXJOAZYINABFFWSFCJMZQHKKWFCXUWUNEEJBLRULUMTRWECEDWDYJCWMHUOJWLPZLAAIKHTCVNSZHCWSXNVBNAHEOMZOENVDYZCKUAAKZDYELWEWYVGEMMSYQHVBWPUJCWDHLXYQHLOYQHUFWDGFOYQHVBOALSOFTUSOMZXJOAZFVLWZELOFRNZQVQLNSKEYECUTUWDOUXDOFIICVW"
t = 'UNUPMESBIUODMVQAZFSWMUWAVNFDCAWAVNEAZIRJPVHNSBQJBRHNVVFDBFHNSRQJMAVEKUHNPNEAVJLNIHFDMVQAVZDNBRULNNKHQUUSMEGABVKJAPKKVARYPFHDMADXMEHEORQPTVFDPRLOAGGAZTDNVVFDBZDNBRULNNKHABQZMEQPWGHICAGEAGGWAMHEKUHJLRVOBNPIMFKAZELJLVDJMEVEVQVEMRLJAVRQFVQZQNQAZBGAZRLJICDYPRKAQAHNENUOQPKJQPKPAVFDMEZEMVQZQNQAZNQVCEHZMAVEVQDXMEHNJRPQMUWAAVFDLNVCMFSNIRFDQAJWVTCQPNOPMAPAQAHHQREAVSUACAGAQPKDMVVOMALYPGKAZELJLVDJMEXJLNXYPALYPGJNWFVAZODAZBGAZFRWMUQHQPKEKUKAQFVASBQNIQXJLVFDJVQQMOHNPNXLBXHEVVQZQNQAZVFDJVQBQYPOKUDQACLATRUQVQZEZQUAPRQDQRUAQAHJQAGEIAHNNVOIPRLJMEJQKXWARNVIQADJCAGFIFPEVUHEVRUZIAQCCPNPMAVEMOHELRNKVEDZIAXJLQDJVOUQMYOPMAVEMNOHMYRODBUHIPKAVFDCBZDHSBQNIQKEMYWOQPKZMAEWCPKQVQMWXFWAVNFDTHIPANJPUNOSCFVPMGLDZQDOVVFDBIRNTNXPMEOWKUHJTVHBMALDUGUWMAHJLVHSIAJAVUHNCAWAZHQZDRUOKUPEMEWAVQLAONQVMFFDUVQGMWDOUVQQVQKAQAHNAPKQMGWATGHJLVHGWRSBMFLAENUAVQXNKUGAVYDYPNQBIYOOWNXOARUWBRPZIFVOQRNAQAHJBBQDMEDQAOUWKUWAVQLALEHEENUAVNPNIAGALRVZWEIAANQCMXRIURQQVQDHTRGAVRQOQREAORJJMGHJAPKWCGHJAVHAVGJAQFWAZGDJMVQARHQCMSUWCGUWBNXBAVHVCHQZNEDC'