// Arup Guha
// 8/31/2021
// Code written to solve question 3 on CIS 3362 Homework #1.

// This code tries all 312 possible affine decryption keys, but in the potential plaintext
// searches for the strings "the", "with" and "for" and only prints out candidates with
// one of these strings.

#include <stdio.h>
#include <string.h>

// Valid values of a.
const int A_KEYS[] = {1,3,5,7,9,11,15,17,19,21,23,25};

#define NUMCOMMON 3
const char COMMON[3][5] = {"the", "with", "for"};

// Functions I use.
int contains(char* str);
int hasWord(const char* str, const char* sub);

int main(void) {

    // Read the ciphertext.
    char cipher[1000];
    scanf("%s", cipher);
    int len = strlen(cipher);

    // a isn't the real a, it's an index into A_KEYS...
    for (int a=0; a<12; a++) {

        // Look through 25 possible keys (answer isn't 0)
        for (int b=0; b<26; b++) {

            // Store potential plaintext here.
            char temp[1000];

            // Subtract dec and take care of mod stuff to decrypt.
            for (int i=0; i<len; i++)
                temp[i] = (A_KEYS[a]*(cipher[i]-'a')+b)%26 + 'a';
            temp[len] = '\0';

            // Don't print stuff that is unlikely.
            if (!contains(temp)) continue;

            // Print the possible key.
            printf("Dec Key %d %d: %s\n", A_KEYS[a], b, temp);
        }
    }

    return 0;
}

// Returns 1 iff str contains one of the strings in COMMON.
int contains(char* str) {

    // Go through each common word. Return 1 if any are found.
    for (int i=0; i<NUMCOMMON; i++)
        if (hasWord(str, COMMON[i]))
            return 1;

    // None were found if we get here.
    return 0;
}

// Returns 1 iff str contains sub.
int hasWord(const char* str, const char* sub) {

    int strLen = strlen(str);
    int subLen = strlen(sub);

    // Try each starting position in str.
    for (int i=0; i<=strLen-subLen; i++) {

        // Look character by character.
        int ok = 1;
        for (int j=0; j<subLen; j++)
            if (str[i+j] != sub[j])
                ok = 0;

        // found it.
        if (ok) return 1;
    }

    // Never found it if we get here.
    return 0;
}