#include <stdio.h>
#include <time.h>
#include <string.h>

class Permutations
{
    inline void _swap(int &x, int &y) { int h = x; x = y; y = h; }
public:
    Permutations(int val_n, bool *range = 0) : n(val_n), _more(true), _range(range)
    {
        a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = i;
    }
    ~Permutations()
    {
        delete []a;
    }
    bool more() { return _more; }
    void next()
    {
        _more = false;
        int k = n;
        for (int i = n-2; i >= 0; i--)
            if (_range != 0 && !_range[i])
            {
                k = i+1;
            }
            else if (a[i] < a[i+1])
            {
                _more = true;
                for (int j = k-1; j > i; j--)
                    if (a[j] > a[i])
                    {
                        _swap(a[j], a[i]);
                        break;
                    }
                i++;
                for (int j = k-1; j > i; j--, i++)
                    _swap(a[j], a[i]);
                for (int j = k; j < n; j++)
                    a[j] = j;
                break;
            }
    }
    inline int operator[](int i) { return a[i]; }
    int n;
    int *a;
private:
    bool _more;
    bool *_range;
};

FILE *fresults = 0;

long gcd(long a, long b)
{
    while (b != 0)
    {
        long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long lcm(long a, long b)
{
    return a * (b / gcd(a, b));
}

inline long sumUpTo(long n) { return n*(n+1)/2; }

#define ROUND_UP_DIV(X,Y) (((X)+(Y)-1)/(Y))


#define MAX_N 40
#define MAX_PIECES 100
#define MAX_NR_SET 200000
bool selected[MAX_NR_SET+1];
int sel_values[100];
int nr_sel_values = 0;
int n;
long basemul; // = base * multiplier
long divn; // = basemul/n;

bool found_set;

int assigned_to[MAX_NR_SET+1];
int buckets[MAX_N];


bool knapsack(int nr_buckets, int nr_buckets_in_use, int sel[], int nrsel, int left, FILE* fout)
{
    if (left == 0)
    {
        if (nr_buckets == nr_buckets_in_use)
        {
            if (fout)
            {
                for (int b = 0; b < nr_buckets; b++)
                {
                    const char *sep = " ";
                    for (int i = 0; i < nrsel; i++)
                        if (assigned_to[sel[i]] == b)
                        {
                            fprintf(fout, "%s%d", sep, sel[i]);
                            sep = "+";
                        }
                }
            }
            return true;
        }
        return false;
    }
    left--;
    
    // Skip buckets that are full
    int i_first = 0;
    while (buckets[i_first] == 0)
        i_first++;
    
    int value = sel[left];
    // If there is an exact fit for the value at hand in one of
    // the half filled buckets, take it, because any solution
    // that has this value in some other bucket, can be made
    // by swapping the other values that need to be put in this
    // bucket with that value.
    for (int i = i_first; i < nr_buckets_in_use; i++)
        if (buckets[i] - value == 0)
        {
            assigned_to[value] = i;
            buckets[i] -= value;
            if (knapsack(nr_buckets, nr_buckets_in_use, sel, nrsel, left, fout))
                return true;
            buckets[i] += value;
            return false;
        }
    
    // See if the value fits in one of the half filled buckets
    for (int i = i_first; i < nr_buckets_in_use; i++)
        if (buckets[i] - value >= 0)
        {
            assigned_to[value] = i;
            buckets[i] -= value;
            if (knapsack(nr_buckets, nr_buckets_in_use, sel, nrsel, left, fout))
                return true;
            buckets[i] += value;
        }
    
    // If there is still a bucket that is not filled at all, try it:
    if (nr_buckets_in_use < nr_buckets)
    {
        assigned_to[value] = nr_buckets_in_use;
        buckets[nr_buckets_in_use] -= value;
        if (knapsack(nr_buckets, nr_buckets_in_use+1, sel, nrsel, left, fout))
            return true;
        buckets[nr_buckets_in_use] += value;
    }    
    return false;
}

int nr_buckets;
int bucket_size;

bool knapsack2(int bucket_nr, int sel_left)
{
    if (bucket_nr == nr_buckets)
        return true;
    sel_left--;

    for (int i = 0; i < nr_sel_values; i++)
        if (assigned_to[sel_values[i]] == -1 && buckets[bucket_nr] >= sel_values[i])
        {
            assigned_to[sel_values[i]] = bucket_nr;
            buckets[bucket_nr] -= sel_values[i];
            int add = buckets[bucket_nr] == 0 ? 1 : 0;
            if (   sel_left > 3 * (nr_buckets - bucket_nr - 1) - add
                && knapsack2(bucket_nr+add, sel_left))
                return true;
            buckets[bucket_nr] += sel_values[i];
            assigned_to[sel_values[i]] = -1;
            if (buckets[bucket_nr] == bucket_size)
                break;
        }
    
    return false;
}

long tried;

void printSolution(int sel[], int nrsel, FILE* fout)
{
    fprintf(fout, "\n%d set: ", n);
    for (int j = 1; j <= divn; j++)
        if (selected[j])
            fprintf(fout, " %d", j);
    fprintf(fout, "\n");
    for (nr_buckets = n/2 > 1 ? n/2+1 : 2; nr_buckets <= n; nr_buckets++)
    {
        for (int j = 0; j < nr_buckets; j++)
            buckets[j] = basemul / nr_buckets;
        fprintf(fout, "%d buckets with %d: ", nr_buckets, basemul / nr_buckets);
        knapsack(nr_buckets, 0, sel, nrsel, nrsel, fout);
        fprintf(fout, "\n");
    }
}

int count = 0;

void checkSet()
{
    tried++;

    // See if there are enough pairs
    for (nr_buckets = n-2; nr_buckets > n/2; nr_buckets--)
    {
        int nr_pairs = 3 * nr_buckets - nr_sel_values;
        if (nr_pairs <= 0)
            break;
        
        bucket_size = basemul / nr_buckets;
        for (int i = 0; i < nr_sel_values; i++)
            if (2*sel_values[i]-1 > bucket_size && selected[bucket_size - sel_values[i]])
            {
                if (--nr_pairs == 0)
                    break;
            }
        if (nr_pairs > 0)
            return;
    }

    for (nr_buckets = n-2; nr_buckets > n/2; nr_buckets--)
    {
        bucket_size = basemul / nr_buckets;
        for (int j = 0; j < nr_buckets; j++)
            buckets[j] = bucket_size;
        for (int j = 0; j < nr_sel_values; j++)
            assigned_to[sel_values[j]] = -1;

        int sel_left = nr_sel_values;
        int bucket_nr = 0;        
        for (int i = 0; i < nr_sel_values; i++)
            if (2*sel_values[i]-1 >= bucket_size && selected[bucket_size - sel_values[i]])
            {
                assigned_to[sel_values[i]] = bucket_nr;
                assigned_to[bucket_size - sel_values[i]] = bucket_nr;
                bucket_nr++;
                sel_left -= 2;
            }
        
        if (!knapsack2(bucket_nr, sel_left))
            return;
    }

    found_set = true;
    count++;
    printSolution(sel_values, nr_sel_values, stderr);
    fprintf(stderr, "\n");
    if (fresults != 0)
    {
        printSolution(sel_values, nr_sel_values, fresults);
        fflush(fresults);
    }
}

bool filled[MAX_N][MAX_N];
int to_go_i[MAX_N];
int left_i[MAX_N];
int to_go_j[MAX_N];
int left_j[MAX_N];

int fill_mode[MAX_PIECES];
int fill_i[MAX_PIECES];
int fill_j[MAX_PIECES];
bool fill_other_is_1[MAX_PIECES];

void fill_path(int nr_pieces)
{
    if (nr_pieces == 0)
        return;
    nr_pieces--;
    
    int min_to_go = 1000;
    int minor_min_to_go = 1000;
    int pos_i;
    int pos_j;
    int mode;
    for (int i = 0; i < n; i++) if (to_go_i[i] > 0)
        for (int j = 0; j < n; j++) if (to_go_j[j] > 0)
            if (filled[i][j])
                if (to_go_i[i] == 1 && to_go_j[j] == 1)
                {
                    fill_mode[nr_pieces] = 0;
                    fill_i[nr_pieces] = i;
                    fill_j[nr_pieces] = j;
                    filled[i][j] = false;
                    to_go_i[i]--;
                    to_go_j[j]--;
                    fill_path(nr_pieces);
                    to_go_j[j]++;
                    to_go_i[i]++;
                    filled[i][j] = true;
                    return;
                }
                else if (to_go_i[i] <= to_go_j[j])
                {
                    if (to_go_i[i] < min_to_go || (to_go_i[i] == min_to_go && to_go_j[j] < minor_min_to_go))
                    {
                        min_to_go = to_go_i[i];
                        mode = min_to_go == 1 ? 1 : 3;
                        minor_min_to_go = to_go_j[j];
                        pos_i = i;
                        pos_j = j;
                    }
                }
                else
                {
                    if (to_go_j[j] < min_to_go || (to_go_j[j] == min_to_go && to_go_i[i] < minor_min_to_go))
                    {
                        min_to_go = to_go_j[j];
                        mode = min_to_go == 1 ? 2 : 3;
                        minor_min_to_go = to_go_i[i];
                        pos_i = i;
                        pos_j = j;
                    }
                }
    
    fill_mode[nr_pieces] = mode;
    fill_i[nr_pieces] = pos_i;
    fill_j[nr_pieces] = pos_j;
    filled[pos_i][pos_j] = false;
    to_go_i[pos_i]--;
    to_go_j[pos_j]--;
    fill_path(nr_pieces);
    to_go_j[pos_j]++;
    to_go_i[pos_i]++;
    filled[pos_i][pos_j] = true;
}

void fill_along_path(int nr_pieces)
{
    if (nr_pieces == 0)
    {
        for (int i = 0; i < n; i++)
            if (left_i[i] > 0)
                return;
        for (int j = 0; j < n-1; j++)
            if (left_j[j] > 0)
                return;
        checkSet();
        return;
    }
    nr_pieces--;
    
    int i = fill_i[nr_pieces];
    int j = fill_j[nr_pieces];
    switch (fill_mode[nr_pieces])
    {
        case 0:
        {
            int left = left_i[i];
            if (left > 0 && !selected[left] && left_j[j] == left)
            {
                selected[left] = true;
                sel_values[nr_sel_values++] = left;
                left_i[i] = 0;
                left_j[j] = 0;
                fill_along_path(nr_pieces);
                left_j[j] = left;
                left_i[i] = left;
                nr_sel_values--;
                selected[left] = false;
            }
            break;
        }
        case 1:
        {
            int left = left_i[i];
            if (left > 0 && !selected[left] && left_j[j] > left)
            {
                selected[left] = true;
                sel_values[nr_sel_values++] = left;
                left_i[i] = 0;
                left_j[j] -= left;
                fill_along_path(nr_pieces);
                left_j[j] += left;
                left_i[i] = left;
                nr_sel_values--;
                selected[left] = false;
            }
            break;
        }
        case 2:
        {
            int left = left_j[j];
            if (left > 0 && !selected[left] && left_i[i] > left)
            {
                selected[left] = true;
                sel_values[nr_sel_values++] = left;
                left_i[i] -= left;
                left_j[j] = 0;
                fill_along_path(nr_pieces);
                left_j[j] = left;
                left_i[i] += left;
                nr_sel_values--;
                selected[left] = false;
            }
            break;
        }
        case 3:
        {    
            int left = left_i[i];
            if (left_j[j] < left)
                left = left_j[j];
        
            for (int l = 1; l < left; l++)
            {
                if (!selected[l])
                {
                    selected[l] = true;
                    sel_values[nr_sel_values++] = l;
                    left_i[i] -= l;
                    left_j[j] -= l;
                    fill_along_path(nr_pieces);
                    left_j[j] += l;
                    left_i[i] += l;
                    nr_sel_values--;
                    selected[l] = false;
                }
            }
            break;
        }
    }    
}

class DivisionsIterator
{
public:
    DivisionsIterator(int buckets, int pieces, bool one) : _pieces(pieces), _buckets(buckets)
    {
        _i = 0;
        if (one)
        {
            _div[_i++] = 1;
            _pieces--;
        }
        while (_i < buckets-1)
        {
            _div[_i++] = 2;
            _pieces -= 2;
        }
        _div[_i] = _pieces;
    }
    bool more() { return _i > 0; }
    void next()
    {
        _i--;
        for (; _i >= 0; _i--)
        {
            int v = _div[_i] + 1;
            if (v * (_buckets-_i-1) + 1 <= _pieces)
            {
                _div[_i++]++;
                _pieces--;
                while (_i < _buckets-1)
                {
                    _div[_i++] = v;
                    _pieces -= v;
                }
                _div[_i] = _pieces;
                return;
            }
            _pieces += _div[_i];
        }
    }
    
    int operator[](int i) { return _div[i]; }
private:
    int _pieces;
    int _buckets;
    int _div[MAX_N];
    int _i;
};


void solve(int tot_nr_pieces)
{
    fprintf(stderr, "solve n=%d ", n);
    for (DivisionsIterator divisionIt1(n, tot_nr_pieces, true); divisionIt1.more(); divisionIt1.next())
    {
        for (DivisionsIterator divisionIt2(n-1, tot_nr_pieces, false); divisionIt2.more(); divisionIt2.next())
        {
            for (int i = 0; i < n; i++)
                fprintf(stderr, "%d ", divisionIt1[i]);
            fprintf(stderr, " -  ");
            for (int j = 0; j < n-1; j++)
                fprintf(stderr, "%d ", divisionIt2[j]);
            fprintf(stderr, "\n");

            int placed_i[MAX_N];
            for (int i = 0; i < n; i++)
                placed_i[i] = 0;
            int placed_j[MAX_N];
            for (int j = 0; j < n-1; j++)
                placed_j[j] = 0;
            
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n-1; j++)
                    filled[i][j] = false;
                    
            int i = 0;
            int j = 0;
            int p = 0;
            while (j >= 0)
            {
                while (i < n && j < n-1)
                {
                    if (   placed_i[i] < divisionIt1[i] && placed_j[j] < divisionIt2[j]
                        && !(i > 0 && divisionIt1[i-1] == divisionIt1[i] && placed_i[i-1] == 0))
                    {
                        filled[i][j] = true;
                        placed_i[i]++;
                        placed_j[j]++;
                        p++;
                    }
                    bool not_full = (i == n-1 && placed_j[j] < divisionIt2[j]);
                    
                    i++; if (i == n) { i = 0; j++; }
                    
                    if (not_full)
                        break;
                }
                
                if (p == tot_nr_pieces)
                {
                    bool smaller = false;
                    bool range[MAX_N];
                    for (int j = 0; j < n-2; j++)
                        range[j] = divisionIt2[j] == divisionIt2[j+1];
                    
                    for (Permutations j_perm(n-1, range); j_perm.more() && !smaller; j_perm.next())
                    {
                        bool equal = true;
                        for (int j = 0; j < n-1 && equal; j++)
                            equal = divisionIt2[j] == divisionIt2[j_perm[j]];
                        if (equal)
                        {
                            int cmp = 0;
                            bool used[MAX_N];
                            for (int i = 0; i < n; i++)
                                used[i] = false;
                            for (int i = 0; i < n && cmp == 0; i++)
                            {
                                int i1 = 0;
                                while (i1 < n && (used[i1] || divisionIt1[i1] != divisionIt1[i]))
                                    i1++;
                                for (int i2 = i1+1; i2 < n; i2++)
                                    if (!used[i2] && divisionIt1[i2] == divisionIt1[i])
                                    {
                                        int cmp2 = 0;
                                        for (int j = 0; j < n-1 && cmp2 == 0; j++)
                                            if (filled[i1][j_perm[j]] != filled[i2][j_perm[j]])
                                                cmp2 = filled[i1][j_perm[j]] ? 1 : -1;
                                        if (cmp2 < 0)
                                            i1 = i2;
                                    }
                                used[i1] = true;

                                for (int j = 0; j < n-1 && cmp == 0; j++)
                                    if (filled[i][j] != filled[i1][j_perm[j]])
                                        cmp = filled[i][j] ? 1 : -1;
                            }
                            if (cmp < 0)
                                smaller = true;
                        }
                    }    
                    
                    if (!smaller)
                    {    
                        for (int i = 0; i < n; i++)
                        {
                            for (int j = 0; j < n-1; j++)
                                fprintf(stderr, "   %c", filled[i][j] ? 'X' : '_');
                            fprintf(stderr, "\n");
                        }
                        fprintf(stderr, "\n");
                        for (int i = 0; i < n; i++)
                        {
                            to_go_i[i] = divisionIt1[i];
                            left_i[i] = divn;
                        }
                        for (int j = 0; j < n-1; j++)
                        {
                            to_go_j[j] = divisionIt2[j];
                            left_j[j] = basemul/(n-1);
                        }

                        fill_path(tot_nr_pieces);
                        fill_along_path(tot_nr_pieces);
                    }
                }
                for (;;)
                {
                    if (i == 0) { i = n-1; j--; } else i--;
                    
                    if (j < 0)
                        break;
                        
                    if (filled[i][j])
                    {
                        filled[i][j] = false;
                        placed_i[i]--;
                        placed_j[j]--;
                        p--;
                        
                        i++; if (i == n) { i = 0; j++; }
                        break;
                    }
                }
            }
        }
    }
}



int main(int argc, char *argv[])
{
    fresults = fopen("chocobar_results.txt", "wt");

    clock_t start_time = clock();

    long base = 1;
    for (n = 1; n <= 9; n++)
    {
        base = lcm(base, n);
        if (n < 7)
            continue;
        long max = base / n;
        fprintf(stderr, "%ld : %ld %ld ", n, base, max);
        
        long min_multiple = 1;
        while (sumUpTo(max * min_multiple) < base)
            min_multiple++;
        fprintf(stderr, "  need %ld %ld\n", min_multiple, base * min_multiple);

        // Generate all sets
        found_set = false;
        for (int tot_nr_pieces = 2*n/*-1*/; !found_set && tot_nr_pieces <= 2*n+1; tot_nr_pieces++)
        {
            fprintf(stderr, "Try %d\n", tot_nr_pieces);
            long multiple = min_multiple;
            basemul = base * multiple;
            divn = basemul/n;

            for (int i = 1; i <= divn; i++)
                selected[i] = false;
            
            solve(tot_nr_pieces);
        }
    }

    clock_t end_time = clock();
    fprintf(stderr, "Elapsed time: %ld\n", end_time - start_time);
    return 0;
}