#include <stdio.h>

#define BIT(V,N) (((V) & (N)) != 0)

bool possible_unfold(int a) { return a == 0 || (a >= 16 && a != 24 && a != 29); }

bool straight_unfold(int a) { return a == 0 || a == 16 || a == 18 || a == 26; }

int rotate_unfold(int a)
{
    return ((a & 1) << 4) | (a & 2) | ((a & 4) << 1) | ((a & 8) >> 3) | ((a & 16) >> 2);
}

int bits_set(int a) { return (a & 1) + ((a >> 1) & 1) + ((a >> 2) & 1) + ((a >> 3) & 1) + ((a >> 4) & 1) + ((a >> 5) & 1) + ((a >> 6) & 1) + ((a >> 7) & 1); }

void print_unfold(int a)
{
    printf(" %d%d%d%d%d", (a >> 4) & 1, a & 1, (a >> 1) & 1, (a >> 2) & 1, (a >> 3) & 1);
}

struct Tile
{
    int i;
    int j;
    int k;
    int k_mode;
    int l;
    int l_mode;
    bool is_empty;
    Tile *next;
    Tile(int n_i, int n_j, int n_k, int n_k_mode, int n_l, int n_l_mode, Tile *n_next)
     : i(n_i), j(n_j), k(n_k), k_mode(n_k_mode), l(n_l), l_mode(n_l_mode), is_empty(i == 0 && j == 0 && k == 0 && l == 0), next(n_next) {}
};

Tile *tiles[32][4][32][4];

    int unfold_invert[32];

int nr_tiles = 0;
void gen_tiles()
{
    for (int i = 0; i < 16; i++)
        unfold_invert[i] = 0;
    for (int i = 16; i < 32; i++)
        unfold_invert[i] =   (i & 16)
                           | ((i & 1) ? 0 : 4) 
                           | ((i & 2) ? 0 : 8) 
                           | ((i & 4) ? 0 : 1) 
                           | ((i & 8) ? 0 : 2);

    for (int i = 0; i < 32; i++)
        for (int i_mode = 0; i_mode < 4; i_mode++)
            for (int j = 0; j < 32; j++)
                for (int j_mode = 0; j_mode < 4; j_mode++)
                    tiles[i][i_mode][j][j_mode] = 0;
    tiles[0][0][0][0] = new Tile(0, 0, 0, 0, 0, 0, 0);
    
    for (int i = 0; i < 32; i++)
        if (possible_unfold(i))
        {
            int i_rot = rotate_unfold(i);
            
            for (int j = 0; j < 32; j++) 
                if (possible_unfold(j) && (i_rot & j) == 0)
                {
                    int ij_rot = rotate_unfold(i_rot | j);
                    
                    for (int k = 0; k < 32; k++)
                        if (possible_unfold(k) && (ij_rot & k) == 0)
                        {
                            int ijk_rot = rotate_unfold(ij_rot | k);
                            
                            int l = 31 & ~ijk_rot;
                            if (possible_unfold(l))
                            {
                                for (int i_mode = 0; i_mode < 4; i_mode++)
                                {
                                    int k_mode = k == 0 ? 0 : i_mode | (j != 0 ? 1 : 0) | (l != 0 ? 2 : 0); 
                                    if (   (i_mode != 0 || straight_unfold(i))
                                        && (k_mode != 3 || straight_unfold(k))
                                        && ((i_mode & 1) == 0 || j == 0)
                                        && ((i_mode & 2) == 0 || l == 0)) 
                                    {
                                        for (int j_mode = 0; j_mode < 4; j_mode++)
                                        {
                                            int l_mode = l == 0 ? 0 : j_mode | (i != 0 ? 1 : 0) | (k != 0 ? 2 : 0); 
                                            if (   (j_mode != 0 || straight_unfold(j))
                                                && (l_mode != 3 || straight_unfold(l))
                                                && ((j_mode & 1) == 0 || i == 0)
                                                && ((j_mode & 2) == 0 || k == 0)) 
                                            {
                                                tiles[i][i_mode][j][j_mode] = new Tile(i, j, unfold_invert[k], k_mode, unfold_invert[l], l_mode, tiles[i][i_mode][j][j_mode]);
                                                nr_tiles++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                }
        } 
}

#define SIZE 19
#define CENTER 9

bool possible[32][4][32][4];


void calc_impossible_combinations()
{
    int faces[4][4] = {
        {  0,  3,  5, -1 },
        {  4,  6,  3,  1 },
        {  7,  4,  2, -1 },
        {  7, -1,  5,  6 },
    };
    
    int dir[7][2] = {
        {  0, -1 },
        { -1,  0 },
        {  0,  1 },
        {  1,  0 },
        {  0, -1 },
        { -1,  0 },
        {  0,  1 },
    };
    
    struct Pattern
    {
        int n;
        bool above;
        bool below;
        int i_s[5];
        int j_s[5];
        Pattern *next;
        Pattern(Pattern *n_next) : n(0), above(false), below(false), next(n_next) {}
        void add(int i, int j)
        {
            i_s[n] = i;
            j_s[n] = j;
            n++;
            if (j < 0)
                below = true;
            else if (j > 0)
                above = true;
        }
    };


    Pattern *patterns[32];

    for (int a = 0; a < 16; a++)
        patterns[a] = new Pattern(0);
    for (int a = 16; a < 32; a++)
        patterns[a] = 0;
    
    int sides[8] = { 1 + 16, 2 + 16, 4 + 16, 1 + 2, 2 + 4, 1 + 8, 2 + 8, 4 + 8 };

    for (int a = 16; a < 32; a++)
        if (possible_unfold(a))
        {
            int nr_faces = bits_set(a) - 1;
            
            int possible_sides = 0;
            for (int i = 0; i < 8; i++)
                if ((a & sides[i]) == sides[i])
                    possible_sides |= (1 << i);

            for (int sel_sides = 0; sel_sides < 256; sel_sides++)
                if ((sel_sides & possible_sides) == sel_sides && bits_set(sel_sides) == nr_faces)
                {
                    char field[SIZE][SIZE];
                    for (int i = 0; i < SIZE; i++)
                        for (int j = 0; j < SIZE; j++)
                            field[i][j] = ' ';
        
                    field[CENTER][CENTER] = '#';
                    field[CENTER][CENTER-1] = 'a' + 0;
                    field[CENTER+1][CENTER] = 'a' + 1;
                    field[CENTER][CENTER+1] = 'a' + 2;
                    
                    int avail_faces = a - 16;
                    int avail_sides = sel_sides;
                    
                    // loop for number faces minus one
                    bool okay = true;
                    for (int n = 0; n < nr_faces; n++)
                    {
                        // Loop over the faces that have not been placed yet
                        for (int i = 1; i < SIZE; i += 2)
                            for (int j = 1; j < SIZE; j += 2)
                                if (field[i][j] == ' ')
                                    for (int r = 0; r < 4; r++)
                                    {
                                        char c = field[i + dir[r][0]][j + dir[r][1]];
                                        if ('a' <= c && c < 'a' + 8)
                                        {
                                            c -= 'a';
                                            if ((avail_sides & (1 << c)) != 0)
                                                for (int p = 0; p < 4; p++)
                                                    if ((avail_faces & (1 << p)) != 0)
                                                        for (int k = 0; k < 4; k++)
                                                            if (faces[p][k] == c)
                                                            {
                                                                avail_sides &= ~(1 << c);
                                                                avail_faces &= ~(1 << p);
                                                                field[i][j] = 'A' + p;
                                                                for (int r2 = 1; r2 < 4; r2++)
                                                                    if (faces[p][(k + r2)%4] != -1)
                                                                        field[i + dir[r+r2][0]][j + dir[r+r2][1]] = 'a' + faces[p][(k + r2)%4];
                                                                goto found;
                                                            }
                                        }
                                    }
                        okay = false;
                        break;
                        found:;
                    }
                    if (okay)
                    {
                        patterns[a] = new Pattern(patterns[a]);
                        int min_i = SIZE + 1;
                        int max_i = 0;
                        int min_j = SIZE + 1;
                        int max_j = 0;
                        for (int j = 1; j < SIZE; j += 2)
                            for (int i = 1; i < SIZE; i += 2)
                                if (field[i][j] != ' ')
                                {
                                    patterns[a]->add((i - CENTER)/2, (j - CENTER)/2);
                                    if (i < min_i) min_i = i;
                                    if (i > max_i) max_i = i;
                                    if (j < min_j) min_j = j;
                                    if (j > max_j) max_j = j;
                                }
                    }
                }
        }
            
    
    for (int i1 = 0; i1 < 32; i1++)
        for (int i1_mode = 0; i1_mode < 4; i1_mode++)
        {
            bool above1 = (i1_mode & 1) == 0;
            bool below1 = (i1_mode & 2) == 0;

            for (int i2 = 0; i2 < 32; i2++)
                for (int i2_mode = 0; i2_mode < 4; i2_mode++)
                {
                    bool above2 = (i2_mode & 1) == 0;
                    bool below2 = (i2_mode & 2) == 0;

                    bool poss = false;
                    for (Pattern *p1 = patterns[i1]; p1 != 0 && !poss; p1 = p1->next)
                        if ((above1 || !p1->above) && (below1 || !p1->below))
                            for (Pattern *p2 = patterns[i2]; p2 != 0 && !poss; p2 = p2->next)
                                if ((above2 || !p2->above) && (below2 || !p2->below))
                                {
                                    poss = true;
                                    for (int j1 = 0; j1 < p1->n && poss; j1++)
                                        for (int j2 = 0; j2 < p2->n && poss; j2++)
                                            poss = p1->i_s[j1] != p2->i_s[j2] || p1->j_s[j1] != p2->j_s[j2] - 1;
                                }
                    possible[i1][i1_mode][i2][i2_mode] = poss;
                }
        }
}

#define N 20
#define MAX_NR 1000

struct ColumnList;

struct Column
{
    int values[N];
    int modes[N];
    int min_nr_empty;
    bool empties[12];
    bool reachable;
    ColumnList *next_columns;
    ColumnList *prev_columns;
    Column *next;
    Column() : min_nr_empty(MAX_NR), next_columns(0), prev_columns(0), reachable(false), next(0)
    {
        for (int i = 0; i < N; i++)
            values[i] = modes[i] = 0;
        for (int i = 0; i < 12; i++)
            empties[i] = 0;
    }
    
    void print(FILE *f, int n)
    {
        fprintf(f, "##\n");
        for (int i = 0; i < n; i++)
        {
            if (i > 0)
                fprintf(f, "\n");
            fprintf(f, "    %d\n", BIT(values[i],1));
            fprintf(f, "%d %d%d%d\n", modes[i], BIT(values[i], 8), BIT(values[i], 2), BIT(values[i], 16)); 
            fprintf(f, "    %d\n", BIT(values[i],4));
        }
        fprintf(f, "##\n");
    }
};

struct ColumnList
{
    Column* prev_column;
    Column* next_column;
    int nr_empty;
    ColumnList *next_columns;
    ColumnList *prev_columns;
    int values[N-1];
    ColumnList(Column* n_prev_column, Column* n_next_column, int n_nr_empty) 
     : prev_column(n_prev_column), next_column(n_next_column), nr_empty(n_nr_empty)
    {
        next_columns = prev_column->next_columns;
        prev_column->next_columns = this;
        prev_columns = next_column->prev_columns;
        next_column->prev_columns = this;
    }
};


Column *columns = 0;
int nr_columns = 1;
int nr_transitions = 0;

void expand_column(Column* column, int p, int n, int j, int j_mode, int nr_empty, Tile *sel_tiles[])
{
    if (p == n)
    {
        if (j == 0)
        {
            nr_transitions++;
            Column** ref_column = &columns;
            for (; *ref_column != 0; ref_column = &(*ref_column)->next)
            {
                bool equal = true;
                for (int q = 0; q < n; q++)
                    if (   (*ref_column)->values[q] != sel_tiles[q]->k
                        || (*ref_column)->modes[q] != sel_tiles[q]->k_mode)
                    {
                        equal = false;
                        break;
                    }
                if (equal)
                    break;
            }
            if (*ref_column == 0)
            {
                nr_columns++;
                (*ref_column) = new Column();
                for (int q = 0; q < n; q++)
                {
                    (*ref_column)->values[q] = sel_tiles[q]->k;
                    (*ref_column)->modes[q] = sel_tiles[q]->k_mode;
                }
            }
            if ((*ref_column)->min_nr_empty > column->min_nr_empty + nr_empty)
                (*ref_column)->min_nr_empty = column->min_nr_empty + nr_empty;
            ColumnList *trans = new ColumnList(column, *ref_column, nr_empty);
            for (int q = 0; q < n - 1; q++)
                trans->values[q] = sel_tiles[q]->l;
        }        
        return;
    }
    
    int i = column->values[p];
    int i_mode = column->modes[p];
    for (Tile *tile = tiles[i][i_mode][j][j_mode]; tile != 0; tile = tile->next)
    {
        if (p == 0
            || possible[unfold_invert[sel_tiles[p - 1]->k]]
                       [sel_tiles[p - 1]->k_mode | (p - 1 == 0 ? 1 : 0)]
                       [unfold_invert[tile->k]]
                       [tile->k_mode | (p == n - 1 ? 2 : 0)])
        {
            sel_tiles[p] = tile;
            expand_column(column, p + 1, n, tile->l, tile->l_mode, nr_empty + (tile->is_empty ? 1 : 0), sel_tiles);
        }
    }
} 

void build_graph(int n)
{
    columns = new Column();
    columns->min_nr_empty = 0;
    columns->empties[0] = true;
    int nr = 0;
    for (Column *column = columns; column != 0; column = column->next)
    {
        if (nr % 100 == 0)
            printf("%d %d %d\n", nr, nr_columns, nr_transitions);
        nr++;
        Tile *sel_tiles[N];
        expand_column(column, 0, n, 0, 0, 0, sel_tiles);
    }
}

int height = 6;

Column *sel_columns[30];
ColumnList *sel_trans[30];

int length = 10;

void print_sols(Column *column, int depth, int nr_empty)
{
    sel_columns[depth] = column;
    if (depth == length || (depth > 0 && column == columns))
    {
        for (int d = 1; d <= depth; d++)
            printf("+--");
        printf("+\n");
        for (int h = 0; h < height; h++)
        {
            printf("|");
            for (int d = 1; d <= depth; d++)
                printf("  %c", sel_columns[d]->values[h] == 0 ? '|' : ' ');
            printf("\n");
            if (h < height - 1)
            {
                printf("+");
                for (int d = 0; d < depth; d++)
                    printf("%s+", sel_trans[d]->values[h] == 0 ? "--" : "  ");
                printf("\n");
            }
        }
        for (int d = 1; d <= depth; d++)
            printf("+--");
        printf("+\n\n");
        
        return;
    }
    
    if (nr_empty > 10)
        return;
    
    for (ColumnList *next_column = column->next_columns; next_column != 0; next_column = next_column->next_columns)
        if (next_column->next_column->reachable)
        {
            sel_trans[depth] = next_column;
            print_sols(next_column->next_column, depth + 1, nr_empty + next_column->nr_empty);
        }
}      

int main(int argc, char *argv[])
{
    gen_tiles();

    calc_impossible_combinations();
    
    
    printf("%d\n", nr_tiles);
    
    build_graph(height);
    printf("%d %d ", nr_columns, nr_transitions);
    
    int nr_reachable = 1;
    columns->reachable = true;
    for (bool more = true; more;)
    {
        more = false;
        for (Column *column = columns; column != 0; column = column->next)
            if (column->reachable)
                for (ColumnList *trans = column->prev_columns; trans != 0; trans = trans->prev_columns)
                    if (!trans->prev_column->reachable)
                    {
                        trans->prev_column->reachable = true;
                        nr_reachable++;
                        more = true;
                    }
    }
    printf("%d\n", nr_reachable);
    
    return 0;
}