#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define CHARS_MAX 64
#define MAX_GATES_PER_WIRE 16
#define MAX_WIRES 16*1024
#define MAX_GATES 8*1024
#define c2i(a) ((a) >= 'a' ? ((a) - 'a') : ((a) - '0' + 26))


int cmp(const void* a, const void* b) {
    const char **pa = (const char**)a;
    const char **pb = (const char**)b;

    if ((*pa)[0] != (*pb)[0]) {
        return (*pa)[0] - (*pb)[0];
    }

    if ((*pa)[1] != (*pb)[1]) {
        return (*pa)[1] - (*pb)[1];
    }

    return (*pa)[2] - (*pb)[2];
}

typedef struct node {
    struct node *children[36];
    struct wire *value;
    char key;
    uint8_t is_leaf;
} node_t;

node_t* create_node() {
    node_t *node = calloc(1, sizeof(node[0]));
    return node;
}

node_t* search(node_t* root, char* word) {
    node_t* node = root;
    for (int i = 0; i < 3; i++) {
        if (node->children[c2i(word[i])] == NULL) {
            return NULL;
        }
        node = node->children[c2i(word[i])];
    }
    return node;
}

void insert(node_t* root, char* word, struct wire *value) {
    node_t* node = root;
    for (int i = 0; i < 3; i++) {
        if (node->children[c2i(word[i])] == NULL) {
            node->children[c2i(word[i])] = create_node();
        }
        node = node->children[c2i(word[i])];
    }
    node->value = value;
    node->is_leaf = 1;
}

void free_node(node_t* node) {
    for (int i = 0; i < 36; i++) {
        if (node->children[i] != NULL) {
            free_node(node->children[i]);
        }
    }

    free(node->value);
    free(node);
}

typedef struct wire {
    char name[3];
    int signal;
    struct gate *gates[MAX_GATES_PER_WIRE];
    int output_gate_count;
    struct gate *generator;
} wire_t;

typedef enum {
    AND,
    OR,
    XOR
} gate_type_t;

typedef struct gate {
    wire_t *inputs[2];
    wire_t *output;
    gate_type_t type;
} gate_t;

void process_wire(wire_t *wire);
uint64_t get_output(node_t *wires, char c);
void reset(node_t *wires);
void set_input1(node_t *wires, uint64_t value);
void set_input2(node_t *wires, uint64_t value);
void backtrack(node_t *wires, wire_t **list, int *list_count, wire_t* wire);
int is_correct(node_t *wires, int i, wire_t **initial_wires);
void get_activated_gates(node_t *wires, gate_t **list, int *list_count);

int main() {
    char *p, *buf, c;

    buf = calloc(CHARS_MAX, sizeof(char));
    p = buf;

    wire_t **initial_wires = calloc(MAX_WIRES, sizeof(wire_t*));
    int initial_wire_count = 0;
    int reading_initial_wires = 1;

    char (*preparsed_gates)[10] = calloc(MAX_GATES, sizeof(preparsed_gates[0]));
    int gate_count = 0;

    while ((c = getchar()) != EOF) {
        *p++ = c;
        if (c != '\n') {
            continue;
        }
        if (reading_initial_wires) {
            if (buf[0] == '\n') {
                reading_initial_wires = 0;
                memset(buf, 0, CHARS_MAX);
                p = buf;
                continue;
            }
            initial_wires[initial_wire_count] = calloc(1, sizeof(wire_t));
            initial_wires[initial_wire_count]->name[0] = buf[0];
            initial_wires[initial_wire_count]->name[1] = buf[1];
            initial_wires[initial_wire_count]->name[2] = buf[2];
            initial_wires[initial_wire_count++]->signal = buf[5] == '1' ? 1 : 0;
        } else {
            preparsed_gates[gate_count][0] = buf[0];
            preparsed_gates[gate_count][1] = buf[1];
            preparsed_gates[gate_count][2] = buf[2];
            preparsed_gates[gate_count][3] = buf[4] == 'A' ? AND : (buf[4] == 'O' ? OR : XOR);
            p = buf;
            while (*p++ != ' ');
            while (*p++ != ' ');
            preparsed_gates[gate_count][4] = p[0];
            preparsed_gates[gate_count][5] = p[1];
            preparsed_gates[gate_count][6] = p[2];
            while (*p++ != ' ');
            while (*p++ != ' ');
            preparsed_gates[gate_count][7] = p[0];
            preparsed_gates[gate_count][8] = p[1];
            preparsed_gates[gate_count][9] = p[2];
            gate_count++;
        }

        memset(buf, 0, CHARS_MAX);
        p = buf;
    }

    free(buf);

    // Create trie of wires
    node_t *wires = create_node();

    // Insert initial wires
    for (int i = 0; i < initial_wire_count; i++) {
        insert(wires, initial_wires[i]->name, initial_wires[i]);
    }

    // Go through gates and extract previously unknown wires
    for (int i = 0; i < gate_count; i++) {
        char* wire_name = &preparsed_gates[i][0];
        node_t *wire = search(wires, wire_name);
        if (wire == NULL || wire->is_leaf == 0) {
            wire_t *value = calloc(1, sizeof(wire_t));
            memcpy(value->name, wire_name, 3);
            value->signal = -1;
            insert(wires, value->name, value);
        }
        wire_name = &preparsed_gates[i][4];
        wire = search(wires, wire_name);
        if (wire == NULL || wire->is_leaf == 0) {
            wire_t *value = calloc(1, sizeof(wire_t));
            memcpy(value->name, wire_name, 3);
            value->signal = -1;
            insert(wires, value->name, value);
        }
        wire_name = &preparsed_gates[i][7];
        wire = search(wires, wire_name);
        if (wire == NULL || wire->is_leaf == 0) {
            wire_t *value = calloc(1, sizeof(wire_t));
            memcpy(value->name, wire_name, 3);
            value->signal = -1;
            insert(wires, value->name, value);
        }
    }

    // Now link everything together
    gate_t *gates = calloc(MAX_GATES, sizeof(gates[0]));
    for (int i = 0; i < gate_count; i++) {
        // Link gate inputs/outputs
        gates[i].type = preparsed_gates[i][3];
        wire_t *wire1 = search(wires, &preparsed_gates[i][0])->value;
        gates[i].inputs[0] = wire1;
        wire_t *wire2 = search(wires, &preparsed_gates[i][4])->value;
        gates[i].inputs[1] = wire2;
        wire_t *wire3 = search(wires, &preparsed_gates[i][7])->value;
        gates[i].output = wire3;

        // Link wires to gates
        wire1->gates[wire1->output_gate_count++] = &gates[i];
        wire2->gates[wire2->output_gate_count++] = &gates[i];
        wire3->generator = &gates[i];
    }
    free(preparsed_gates);

    for (int i = 0; i < initial_wire_count; i++) {
        process_wire(initial_wires[i]);
    }

    uint64_t output = get_output(wires, 'z');

    printf("%lu\n", output);

    char **part2 = calloc(8, sizeof(part2[0]));
    int part2_c = 0;
    wire_t **relevant_gates = calloc(MAX_GATES, sizeof(wire_t*));
    relevant_gates[0] = search(wires, "z00")->value;
    int relevant_gate_count = 1;
    int pc = 1;
    for (int i = 1; i < 64; i++) {
        char buf[4];
        sprintf(buf, "z%02d", i);
        node_t *generator_node = search(wires, buf);
        if (generator_node) {
            backtrack(wires, relevant_gates, &relevant_gate_count, generator_node->value);

            if (!is_correct(wires, i, initial_wires)) {
                gate_t **activated = calloc(MAX_GATES, sizeof(gate_t*));
                gate_t **switchable = calloc(MAX_GATES, sizeof(gate_t*));
                int activated_count = 0;
                int switchable_count = 0;
                get_activated_gates(wires, activated, &activated_count);
                for (int j = 0; j < activated_count; j++) {
                    int found = 0;
                    for (int jj = 0; jj < pc; jj++) {
                        if (relevant_gates[jj] == activated[j]->output) {
                            found = 1;
                            break;
                        }
                    }
                    if (!found) {
                        switchable[switchable_count++] = activated[j];
                    }
                }
                
                // Try to switch each switchable
                int br = 0;
                for (int s1 = 0; s1 < switchable_count; s1++) {
                    for (int s2 = s1 + 1; s2 < switchable_count; s2++) {
                        wire_t *tmp = switchable[s2]->output;
                        switchable[s2]->output = switchable[s1]->output;
                        switchable[s1]->output = tmp;
                        // Check switched version
                        if (is_correct(wires, i, initial_wires)) {
                            part2[part2_c++] = switchable[s1]->output->name;
                            part2[part2_c++] = switchable[s2]->output->name;
                            br = 1;
                            break;
                        }

                        switchable[s1]->output = switchable[s2]->output;
                        switchable[s2]->output = tmp;
                    }
                    if (br) {
                        break;
                    }
                }
                free(activated);
                free(switchable);
            }
            pc = relevant_gate_count;
        }
    }
    qsort(part2, part2_c, sizeof(char*), cmp);

    for (int i = 0; i < part2_c; i++) {
        printf("%c%c%c", part2[i][0], part2[i][1], part2[i][2]);
        if (i != part2_c - 1) {
            printf(",");
        }
    }
    printf("\n");

    free(initial_wires);
    free_node(wires);
    free(gates);
    free(relevant_gates);
    free(part2);
}

int eval_gate(gate_t gate) {
    switch (gate.type) {
        case AND:
            return gate.inputs[0]->signal & gate.inputs[1]->signal;
        case OR:
            return gate.inputs[0]->signal | gate.inputs[1]->signal;
        case XOR:
            return gate.inputs[0]->signal ^ gate.inputs[1]->signal;
    }

    return -1;
}

void process_wire(wire_t *wire) {
    // Try each of its outputs
    for (int i = 0; i < wire->output_gate_count; i++) {
        // Check if gate has both of it's outputs set
        if (wire->gates[i]->inputs[0]->signal != -1 && wire->gates[i]->inputs[1]->signal != -1) {
            wire->gates[i]->output->signal = eval_gate(*wire->gates[i]);
            process_wire(wire->gates[i]->output);
        }
    }
}

void set_input1(node_t *wires, uint64_t value) {
    for (int i = 0; i < INT_MAX; i++) {
        char buf[4];
        sprintf(buf, "x%02d", i);
        node_t *node = search(wires, buf);
        if (node == NULL) {
            break;
        }
        node->value->signal = (value >> i) & 1;
    }
}

void set_input2(node_t *wires, uint64_t value) {
    for (int i = 0; i < INT_MAX; i++) {
        char buf[4];
        sprintf(buf, "y%02d", i);
        node_t *node = search(wires, buf);
        if (node == NULL) {
            break;
        }
        node->value->signal = (value >> i) & 1;
    }
}

uint64_t get_output(node_t *wires, char c) {
    uint64_t result = 0;
    for (int i = 0; i < INT_MAX; i++) {
        char buf[4];
        sprintf(buf, "%c%02d", c, i);
        node_t *node = search(wires, buf);
        if (node == NULL) {
            break;
        }
        result += (uint64_t)node->value->signal << i;
    }
    return result;
}

void reset(node_t *wires) {
    if (wires == NULL) {
        return;
    }

    for (int i = 0; i < 36; i++) {
        reset(wires->children[i]);
    }

    if (wires->value != NULL) {
        wires->value->signal = -1;
    }
}

void backtrack(node_t *wires, wire_t **list, int *list_count, wire_t* wire) {
    if (wire == NULL) {
        return;
    }

    int found = 0;
    for (int i = 0; i < *list_count; i++) {
        if (wire == list[i]) {
            found = 1;
            break;
        }
    }
    if (found) {
        return;
    }
    list[*list_count] = wire;
    (*list_count)++;

    if (wire->generator) {
        backtrack(wires, list, list_count, wire->generator->inputs[0]);
        backtrack(wires, list, list_count, wire->generator->inputs[1]);
    }
}

void get_activated_gates(node_t *wires, gate_t **list, int *list_count) {
    if (wires == NULL) {
        return;
    }
    
    if (wires->value != NULL && wires->value->generator != NULL && wires->value->signal != -1) {
        int found = 0;
        for (int i = 0; i < *list_count; i++) {
            if (wires->value->generator == list[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            list[*list_count] = wires->value->generator;
            (*list_count)++;
        }
    }
    // Iterate each wire
    for (int i = 0; i < 36; i++) {
        get_activated_gates(wires->children[i], list, list_count);
    }
}

int is_correct(node_t *wires, int i, wire_t **initial_wires) {
    for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
            for (int jj = 0; jj < 2; jj++) {
                for (int kk = 0; kk < 2; kk++) {
                    reset(wires);
                    set_input1(wires, ((uint64_t)j << i) + ((uint64_t)k << (i-1)));
                    set_input2(wires, ((uint64_t)jj << i) + ((uint64_t)kk << (i-1)));
                    uint64_t e = ((uint64_t)j << i) + ((uint64_t)k << (i-1)) + ((uint64_t)jj << i) + ((uint64_t)kk << (i-1));
                    char buf[4];
                    for (int ii = 0; ii <= i; ii++) {
                        if (i == 45) {
                            continue;
                        }
                        sprintf(buf, "x%02d", ii);
                        wire_t *x = search(wires, buf)->value;
                        process_wire(x);
                        sprintf(buf, "y%02d", ii);
                        wire_t *y = search(wires, buf)->value;
                        process_wire(y);
                    }

                    for (int ii = 0; ii < i-1; ii++) {
                        sprintf(buf, "z%02d", ii);
                        wire_t *z = search(wires, buf)->value;
                        if (z->signal != 0) {
                            return 0;
                        }
                    }
                    sprintf(buf, "z%02d", i-1);
                    wire_t *z = search(wires, buf)->value;
                    if (z->signal != (k ^ kk)) {
                        return 0;
                    }
                    sprintf(buf, "z%02d", i);
                    z = search(wires, buf)->value;
                    if (z->signal != ((j ^ jj) ^ (k & kk))) {
                        return 0;
                    }
                }
            }
        }
    }

    return 1;
}