#include <stdio.h>

struct Solution
{
    int sides[6];
    int perimeter;
    Solution *next;
    
    Solution() : next(0) {}
    Solution(Solution *sol, Solution *n = 0) : next(n)
    {
        perimeter = sol->perimeter;
        for (int i = 0; i < 6; i++)
            sides[i] = sol->sides[i];
    }
    Solution(Solution &sol) : Solution(&sol, 0) {}
    void assign(Solution &other)
    {
        for (int i = 0; i < 6; i++)
            sides[i] = other.sides[i];
        perimeter = other.perimeter;
    }
    void calc_perimeter()
    {
        perimeter = 0;
        for (int i = 0; i < 6; i++)
            perimeter += sides[i];
    }
    void rotate()
    {
        int h = sides[0];
        for (int i = 0; i + 1 < 6; i++)
            sides[i] = sides[i + 1];
        sides[5] = h;
    }
    void mirror()
    {
        for (int i = 0; i < 3; i++)
        {
            int h = sides[i];
            sides[i] = sides[5 - i];
            sides[5 - i] = h;
        }
    }
    void print(FILE *f)
    {
        fprintf(f, "[");
        for (int i = 0; i < 6; i++)
        {
            if (i > 0) fprintf(f, ", ");
            fprintf(f, "%d", sides[i]);
        }
        fprintf(f, "]:%d", perimeter);
    }
};

int compare(Solution *a, Solution *b)
{
    int r = a->perimeter - b->perimeter;
    for (int i = 0; i < 6 && r == 0; i++)
        r = a->sides[i] - b->sides[i];
    return r;
}

void add_solution(Solution *sol, int n, Solution **ref_sols)
{
    sol->calc_perimeter();
    Solution minimal(sol);
    Solution variant(sol);
    for (int m = 0; m < 2; m++)
    {
        for (int r = 0; r < 6; r++)
        {
            if (compare(&variant, &minimal) < 0)
                minimal.assign(variant);
            variant.rotate();
            
        }
        variant.mirror();
    }
    
    while (*ref_sols != 0 && compare(*ref_sols, &minimal) < 0)
        ref_sols = &(*ref_sols)->next;
    if (*ref_sols == 0 || compare(*ref_sols, &minimal) > 0)
    {
        //printf("  Added %d: ", n);
        //minimal.print(stdout);
        //printf("\n");
        *ref_sols = new Solution(&minimal, *ref_sols);
    }
}       

#define N 100

int main(int argc, char *argv[])
{
    Solution *sols[N];
    for (int i = 0; i < N; i++)
        sols[i] = 0;
    
    {
        Solution first;
        for (int i = 0; i < 6; i++)
            first.sides[i] = 1;
        first.perimeter = 6;
        add_solution(&first, 1, &sols[1]);
    }
    
    for (int i = 0; i < N-1; i++)
        
        for (Solution *sol = sols[i]; sol != 0; sol = sol->next)
        {
            //printf("Expand ");
            //sol->print(stdout);
            //printf("\n");
            
            Solution start(sol);
            
            for (int m = 0; m < 2; m++)
            {
                for (int r = 0; r < 6; r++)
                {
                    Solution sol(start);
                    if (sol.sides[1] == 1 && sol.sides[2] == 1 && i + 1 < N)
                    {
                        sol.sides[0]++;
                        sol.sides[3]++;
                        add_solution(&sol, i + 1, &sols[i + 1]);
                    }
                    else if (sol.sides[1] > 1)
                    {
                        sol.sides[1]--;
                        sol.sides[0]++;
                        sol.sides[2]++;
                        int n = i + sol.sides[1];
                        if (n < N)
                            add_solution(&sol, n, &sols[n]);
                    }
                    start.rotate();
                    
                }
                start.mirror();
            }
        }
    printf("\n");
    for (int i = 1; i < N; i++)
    {
        printf("%d:", i);
        for (Solution *sol = sols[i]; sol != 0; sol = sol->next)
        {
            printf(" ");
            sol->print(stdout);
        }
        printf("\n");
    }
    printf("\n");
    for (int i = 1; i < N; i++)
    {
        int nr = 0;
        for (Solution *sol = sols[i]; sol != 0; sol = sol->next)
            nr++;
        printf("%d,", nr);
    }
    printf("\n");
    for (int i = 1; i < N; i++)
        printf("%d,", sols[i]->perimeter - 6);
    printf("\n");
    
    return 0;
    
}