#include <cstring>//memset.

using namespace std;

class Trie {
public:
    Trie(): m_wdCnt(0) { m_root = new TrieNode(); }
    ~Trie() { clear(); }

    //Return the number of the inserted word.
    //Return -1 if failed (the word already exists or is empty).
    int addWord(const char* str) {
        TrieNode* p = m_root;
        for ( ; *str; str++) {
            int i = *str - 'a';
            if ( !p->child[i] ) { p->child[i] = new TrieNode(); }
            p = p->child[i];
        }
        if (p == m_root || -1 != p->wdNum) { return -1; }
        p->wdNum = m_wdCnt++;
        return p->wdNum;
    }

    void clear() { clear(m_root);  m_wdCnt = 0; }
    
    //Find the number representing the word.
    //Return -1 if not found or an empty string is given.
    int findWord(const char* str) const {
        TrieNode* p = m_root;
        for ( ; *str; str++)
            { p = p->child[*str - 'a'];  if (!p) { return -1; } }
        return p->wdNum;
    }

private:
    struct TrieNode {
        TrieNode* child[26];
        int wdNum;//Number of the word that ends at this level.

        TrieNode(): wdNum(-1) { memset(child, 0, sizeof(child)); }
    };

    void clear(TrieNode* p) {
        for (int i = 0; i < 26; i++)
            { if (p->child[i]) { clear(p->child[i]); } }
        delete p;
    }

    TrieNode* m_root;
    int m_wdCnt;
};


#include <cstdio>
#include <cctype>//islower
#include <string>

const int CIPHER_LEN = 256 + 20;
const int BUF_LEN = 1000000;
const int INF = 99999999;

char g_buf[BUF_LEN + 2];
Trie g_trie;
char g_cipher[CIPHER_LEN + 2];
int g_cipherLen;
//g_minWord[i]: minimun number of words in the substring
//starting with the character i. (i: 0 ~ g_cipherLen - 1)
int g_minWord[CIPHER_LEN + 1];
int g_next[CIPHER_LEN + 1];
//g_minWordNS[i]: similar to g_minWord[i], but only count the situations
//that the first word is NOT SINGLE-LETTER.
int g_minWordNS[CIPHER_LEN + 1];
int g_nextNS[CIPHER_LEN + 1];

bool isWord(const char* str) {
    while (*str) {
        if ( !islower(*str) ) { return false; }
        str++;
    }
    return true;
}

void inputDict() {
    fgets(g_buf, BUF_LEN + 2, stdin);
    int len = strlen(g_buf);
    while (len > 1) {
        g_buf[--len] = '\0';//cover the '\n'.
        if ( len <= CIPHER_LEN && isWord(g_buf) ) {
            g_trie.addWord(g_buf);
        }
        fgets(g_buf, BUF_LEN + 2, stdin);
        len = strlen(g_buf);
    }
}

bool input() {
    fgets(g_cipher, CIPHER_LEN + 2, stdin);
    g_cipherLen = strlen(g_cipher) - 1;
    g_cipher[g_cipherLen] = '\0';
    if ( 0 == strcmp("0", g_cipher) ) { return false; }
    return true;
}

void getMinWord(const int begin) {
    int i = begin;
    while ( i < g_cipherLen ) {
        char temp = g_cipher[i + 1];
        g_cipher[i + 1] = '\0';
        if ( -1 != g_trie.findWord(g_cipher + begin) ) {
            if (begin == i) {
                if (g_minWordNS[i + 1] + 1 < g_minWord[begin]) {
                    g_minWord[begin] = g_minWordNS[i + 1] + 1;
                    g_next[begin] = i + 1;
                }
            }
            else {
                if (g_minWord[i + 1] + 1 < g_minWord[begin]) {
                    g_minWord[begin] = g_minWord[i + 1] + 1;
                    g_next[begin] = i + 1;
                    if (g_minWord[begin] < g_minWordNS[begin]) {
                        g_minWordNS[begin] = g_minWord[begin];
                        g_nextNS[begin] = i + 1;
                    }
                }
            }
        }
        g_cipher[i + 1] = temp;
        i++;
    }
}

void recover() {
    for (int i = 0; i <= g_cipherLen; i++) {
        g_minWord[i] = g_minWordNS[i] = INF;
    }
    g_minWord[g_cipherLen] = g_minWordNS[g_cipherLen] = 0;
    for (int i = g_cipherLen - 1; i >= 0; i--) {
        getMinWord(i);
    }
}

void rotate() {
    for (int i = 0; g_cipher[i]; i++) {
        if ('a' == g_cipher[i]) { g_cipher[i] = 'z'; }
        else { g_cipher[i]--; }
    }
}

string getMsg() {
    string result = "";
    int i = 0;
    int preI = -100;
    while (i < g_cipherLen) {
        if (preI == i - 1) {
            preI = i;
            i = g_nextNS[i];
        }
        else {
            preI = i;
            i = g_next[i];
        }
        string word(g_cipher + preI, g_cipher + i);
        if ( result.size() ) { result += " "; }
        result += word;
    }
    return result;
}

void solve() {
    if ( !isWord(g_cipher) ) {
        printf("NO SOLUTIONS\n");
        return;
    }
    int min = INF, minK;
    string result;
    for (int k = 0; k < 26; k++) {
        recover();
        if (g_minWord[0] < min) {
            min = g_minWord[0];
            minK = k;
            result = getMsg();
        }
        rotate();
    }
    if (INF != min && g_cipherLen > 2 * min) {
        printf( "k=%d: %s\n", minK, result.c_str() );
    }
    else {
        printf("NO SOLUTIONS\n");
    }
}

int main() {
    inputDict();
    while ( input() ) {
        solve();
    }
    return 0;
}