def gcd(q, a):
    while q >= a:
        q = q - a
    if q != 0:
        if gcd(a, q) == 0:
            return q
        else:
            return gcd(a, q)
    else:
        return q


def affineEncode(a, b, c):
    list = []
    ltn = {
    "A" : 0,
    "B" : 1,
    "C" : 2,
    "D" : 3,
    "E" : 4,
    "F" : 5,
    "G" : 6,
    "H" : 7,
    "I" : 8,
    "J" : 9,
    "K" : 10,
    "L" : 11,
    "M" : 12,
    "N" : 13,
    "O" : 14,
    "P" : 15,
    "Q" : 16,
    "R" : 17,
    "S" : 18,
    "T" : 19,
    "U" : 20,
    "V" : 21,
    "W" : 22,
    "X" : 23,
    "Y" : 24,
    "Z" : 25,
    }

    ntl = {
    "0" : "A",
    "1" : "B",
    "2" : "C",
    "3" : "D",
    "4" : "E",
    "5" : "F",
    "6" : "G",
    "7" : "H",
    "8" : "I",
    "9" : "J",
    "10" : "K",
    "11" : "L",
    "12" : "M",
    "13" : "N",
    "14" : "O",
    "15" : "P",
    "16" : "Q",
    "17" : "R",
    "18" : "S",
    "19" : "T",
    "20" : "U",
    "21" : "V",
    "22" : "W",
    "23" : "X",
    "24" : "Y",
    "25" : "Z",
    }

    for i in c:
        x = ltn[i]
        list.append(((a*x)+b)%26)
    ans = ""
    for i in list:
        x = ntl[str(i)]
        ans=ans+x
    return ans





def mmi(a, m):
    if gcd(a, m) == 1:
        x = 1
        s = 1
        while True:
            if s*a > x*m:
                x=x+1
            s=s+1
            if (s*a)-(x*m) == 1:
                return s





def affineDecode(a, b, c):
    list = []
    ltn = {
    "A" : 0,
    "B" : 1,
    "C" : 2,
    "D" : 3,
    "E" : 4,
    "F" : 5,
    "G" : 6,
    "H" : 7,
    "I" : 8,
    "J" : 9,
    "K" : 10,
    "L" : 11,
    "M" : 12,
    "N" : 13,
    "O" : 14,
    "P" : 15,
    "Q" : 16,
    "R" : 17,
    "S" : 18,
    "T" : 19,
    "U" : 20,
    "V" : 21,
    "W" : 22,
    "X" : 23,
    "Y" : 24,
    "Z" : 25,
    }

    ntl = {
    "0" : "A",
    "1" : "B",
    "2" : "C",
    "3" : "D",
    "4" : "E",
    "5" : "F",
    "6" : "G",
    "7" : "H",
    "8" : "I",
    "9" : "J",
    "10" : "K",
    "11" : "L",
    "12" : "M",
    "13" : "N",
    "14" : "O",
    "15" : "P",
    "16" : "Q",
    "17" : "R",
    "18" : "S",
    "19" : "T",
    "20" : "U",
    "21" : "V",
    "22" : "W",
    "23" : "X",
    "24" : "Y",
    "25" : "Z",
    }

    for i in c:
        x = ltn[i]
        list.append((mmi(a, 26)*(x-b))%26)
    ans = ""
    for i in list:
        x = ntl[str(i)]
        ans=ans+x
    return ans

print(affineEncode(5, 8, "AFFINECIPHER"))

print(mmi(5, 26))

print(affineDecode(5, 8, "IHHWVCSWFRCP"))