// Arup Guha
// 8/27/2026
// Code to aid with Fall 2026 CIS 3362 Homework #1
using namespace std;

#include <bits/stdc++.h>

void q12();
void q3();

void printAllShifts(string& cipher);
void decryptShift(string& cipher, int key);
string encryptAffine(string& cipher, int a, int b);
void decryptAffine(string& cipher);

int main() {

    // Used for q1 and q2.
    q3();
    return 0;
}

void q12() {

    // Read string.
    string cipher;
    cin >> cipher;

    // Run the appropriate function call.
    /**
    printAllShifts(cipher);
    decryptShift(cipher, 6);
    **/
}

void q3() {

    // Read string.
    string cipher;
    cin >> cipher;
    decryptAffine(cipher);
}

// Prints all shifts of the string plain. Assumes plain is all lowercase letters.
void printAllShifts(string& cipher) {

    // sub is what I am subtracting.
    for (int sub=0; sub<26; sub++) {

        // Row header.
        cout << sub << ":\t";

        for (int i=0; i<cipher.size(); i++) {

            // Undo addition of key.
            int map = (cipher[i] - 'a' - sub + 26)%26;
            cout << (char)('a'+map);
        }
        cout << endl;
    }
}

// Decrypts cipher for the shift cipher using key as the encryption key.
void decryptShift(string& cipher, int key) {
    for (int i=0; i<cipher.size(); i++) {

        // Undo addition of key.
        int map = (cipher[i] - 'a' - key + 26)%26;
        cout << (char)('a'+map);
    }
    cout << endl;
}

// Brute forces decrypting cipher assuming it was encrypted via the Affine Cipher.
// This prints out all decryption keys and corresponding plaintext that contains the substring "the".
void decryptAffine(string& cipher) {

    for (int a=1; a<26; a++) {

        // Skip these.
        if (gcd(a, 26) != 1) continue;

        for (int b=0; b<26; b++) {

            // Encrypts the cipher with the keys a and b.
            string tmp = encryptAffine(cipher, a, b);

            // If the substring "the" is in tmp, print it along with a and b.
            // If this is plain text, a and b are the DECRYPTION KEYS!
            if (tmp.find("the") != string::npos) {
                cout << tmp.find("the") << " ";
                cout << a << " " << b << " " << tmp << endl;
            }
        }

    }
}

string encryptAffine(string& cipher, int a, int b) {
    string res = "";
    for (int i=0; i<cipher.size(); i++) {
        int tmp = (a*(cipher[i]-'a')+b)%26;
        res = res + (char)('a'+tmp);
    }
    return res;
}

// Returns the gcd of a and b.
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}