// Cook-Levin ejecutado: de una máquina, una entrada y el lado de un tableau, una fórmula.
// Lee la entrada del enunciado y escribe en DIMACS la fórmula del tableau de t × t.
// Ya están la lectura, la numeración de las variables y el grupo 1 de cláusulas.
// Faltan los otros tres grupos: búsquenlos por "Por escribir".
#include <array>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

// ------------------------------------------------------------
// La entrada: una máquina en formato .tm, la cadena w y el lado t del tableau
// ------------------------------------------------------------

struct Move {
    std::string next;  // estado al que pasa
    char write;        // símbolo que escribe
    char dir;          // 'L' o 'R'
};

// N = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm.
struct Ntm {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<char> tape;
    std::map<std::pair<std::string, char>, std::vector<Move>> delta;  // varios movimientos por par
    std::string start;
    std::string accept;
    std::string reject;
};

struct Input {
    Ntm n;
    std::string w;
    int t = 0;
};

std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

Input read_input(std::istream& in) {
    Input input;
    Ntm& n = input.n;
    std::string line;
    bool in_delta = false;
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;  // comentario
        }
        std::vector<std::string> words = split_words(line);
        if (words.empty()) {
            continue;
        }
        if (words[0] == "strings:") {
            break;
        }
        if (in_delta) {
            // estado lee -> destino escribe movimiento
            n.delta[{words[0], words[1][0]}].push_back({words[3], words[4][0], words[5][0]});
        } else if (words[0] == "states:") {
            n.states.assign(words.begin() + 1, words.end());
        } else if (words[0] == "alphabet:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.alphabet.push_back(words[k][0]);
            }
        } else if (words[0] == "tape:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.tape.push_back(words[k][0]);
            }
        } else if (words[0] == "start:") {
            n.start = words[1];
        } else if (words[0] == "accept:") {
            n.accept = words[1];
        } else if (words[0] == "reject:") {
            n.reject = words[1];
        } else if (words[0] == "delta:") {
            in_delta = true;
        }
    }
    std::getline(in, input.w);  // la cadena: una línea vacía es ε
    while (!input.w.empty() && (input.w.back() == '\r' || input.w.back() == ' ')) {
        input.w.pop_back();
    }
    std::string name;
    in >> name >> input.t;  // tableau: t
    return input;
}

// ------------------------------------------------------------
// Las celdas y la numeración de las variables
// ------------------------------------------------------------

// Los símbolos que puede tener una celda, numerados desde 0: primero los de la cinta, en el
// orden de tape:, después los estados, en el orden de states:, y al final #.
struct Cells {
    std::vector<std::string> names;
    int tape_count = 0;
    int state_count = 0;

    int size() const { return static_cast<int>(names.size()); }
    int border() const { return size() - 1; }
    bool is_tape(int s) const { return s < tape_count; }
    bool is_state(int s) const { return s >= tape_count && s < tape_count + state_count; }
    int index(const std::string& name) const {
        for (int s = 0; s < size(); s++) {
            if (names[s] == name) {
                return s;
            }
        }
        return -1;
    }
    int index(char symbol) const { return index(std::string(1, symbol)); }
};

Cells cells_of(const Ntm& n) {
    Cells cells;
    for (char a : n.tape) {
        cells.names.push_back(std::string(1, a));
    }
    for (const std::string& q : n.states) {
        cells.names.push_back(q);
    }
    cells.names.push_back("#");
    cells.tape_count = static_cast<int>(n.tape.size());
    cells.state_count = static_cast<int>(n.states.size());
    return cells;
}

// La variable x_{i,j,s}: "la celda de la fila i y la columna j contiene el símbolo s".
// Filas y columnas de 1 a t; s de 0 a |C| - 1. Son las variables 1, 2, ..., t·t·|C|.
int cell_var(int t, int symbols, int i, int j, int s) {
    return ((i - 1) * t + (j - 1)) * symbols + s + 1;
}

// ------------------------------------------------------------
// La fórmula
// ------------------------------------------------------------

// Una fórmula en CNF. Las cláusulas se guardan una detrás de otra, cada una terminada en 0,
// tal como van en DIMACS.
struct Formula {
    int num_vars = 0;
    long num_clauses = 0;
    std::vector<int> literals;

    int fresh() { return ++num_vars; }  // una variable nueva, para lo que haga falta
    void add(const std::vector<int>& clause) {
        literals.insert(literals.end(), clause.begin(), clause.end());
        literals.push_back(0);
        num_clauses++;
    }
};

void write_dimacs(const Formula& f) {
    std::string text = "p cnf " + std::to_string(f.num_vars) + " " + std::to_string(f.num_clauses) + "\n";
    for (int literal : f.literals) {
        if (literal == 0) {
            text += "0\n";
        } else {
            text += std::to_string(literal);
            text += ' ';
        }
        if (text.size() > (1u << 16)) {
            std::cout << text;
            text.clear();
        }
    }
    std::cout << text;
}

// Grupo 1: cada celda tiene exactamente un símbolo.
void add_cell_clauses(Formula& f, int t, int symbols) {
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= t; j++) {
            std::vector<int> some;
            for (int s = 0; s < symbols; s++) {
                some.push_back(cell_var(t, symbols, i, j, s));
            }
            f.add(some);  // al menos uno
            for (int s = 0; s < symbols; s++) {
                for (int r = s + 1; r < symbols; r++) {
                    f.add({-cell_var(t, symbols, i, j, s), -cell_var(t, symbols, i, j, r)});  // a lo sumo uno
                }
            }
        }
    }
}

// Grupo 2: la primera fila es # q0 w1 ... wn ␣ ... ␣ #.
void add_start_clauses(Formula& f, const Input& input, const Cells& cells) {
    // Por escribir: t cláusulas de un solo literal.
    (void)f;
    (void)input;
    (void)cells;
}

// Una ventana de 2 × 3: a1 a2 a3 arriba, b1 b2 b3 abajo, con los números de Cells.
using Window = std::array<int, 6>;

// Las ventanas legales de N, por las cuatro formas del enunciado.
std::set<Window> legal_windows(const Ntm& n, const Cells& cells) {
    std::set<Window> legal;
    // Por escribir. Por ejemplo, la forma 1 con un movimiento R: para cada línea
    // q a -> r b R de delta y cada x de Γ ∪ {#}, la ventana  x q a / x b r.
    (void)n;
    (void)cells;
    return legal;
}

// Grupo 3: cada ventana de 2 × 3 del tableau es una de las legales.
void add_move_clauses(Formula& f, const std::set<Window>& legal, const Cells& cells, int t) {
    // Por escribir. Por cada posición (i, j) y cada ventana legal, una variable nueva
    // z = f.fresh(), seis cláusulas (¬z ∨ x) y, por posición, la cláusula con todas las z.
    (void)f;
    (void)legal;
    (void)cells;
    (void)t;
}

// Grupo 4: alguna celda contiene q_accept.
void add_accept_clause(Formula& f, const Input& input, const Cells& cells) {
    // Por escribir: una sola cláusula.
    (void)f;
    (void)input;
    (void)cells;
}

int main() {
    Input input = read_input(std::cin);
    Cells cells = cells_of(input.n);
    int t = input.t;
    Formula f;
    f.num_vars = t * t * cells.size();
    add_cell_clauses(f, t, cells.size());
    add_start_clauses(f, input, cells);
    add_move_clauses(f, legal_windows(input.n, cells), cells, t);
    add_accept_clause(f, input, cells);
    write_dimacs(f);
    return 0;
}
