#include <stdio.h>

#define SIZE 17 

void displayGrid(int checkRows[][SIZE]) {
        int i, j, c,colour;

        for(i = 0; i < SIZE; i++)
        {
                for(j = 0; j < SIZE; j++)
                {
                        colour = 0;
                        for(c=0; c<4; c++)
                        {
                                if ((checkRows[c][i] & (1 << j)) == (1 << j))
                                {
                                        colour = c + 1;
                                        break;
                                }
                        }
                        printf("%d  ", colour);
                }

                printf("\n");
        }
        printf("\n\n");
}

int incrementCol(int working, int checkRows[][SIZE]) {
        int i,all,set,current;
        do
        {
                i = 0;
                set = 0;
                while(i < working && !set)
                {
                        all = 0;
                        for(current = 0; current < 4; current++)
                        {
                                if((checkRows[current][i] & (1 << working)) != 0)
                                {
                                        checkRows[current][i] -= (1 << working);
                                        if(current+1 < 4) {
                                                checkRows[current+1][i] += (1 << working);
                                                set = 1;
                                        }
                                        else {
                                                checkRows[0][i] += (1 << working);
                                                i++;
                                        }
                                        all = 1;
                                        break;
                                }
                        }
                        if(i == 4)
                                return 0;
                        if(!all)
                        {
                                checkRows[0][i] += (1 << working);
                                i++;
                        }
                }
        }
        while(isRects(checkRows));
        return 1;
}

int incrementRow(int working, int checkRows[][SIZE]) {
        int i,num, current,compare;
        do {
                num = 0;
                for(current = 0; current < 4; current++)
                {
                        for(i = 0; i <= working; i++)
                        {
                                if(checkRows[current][working] & (1 << working) != 0)           
                                        num += current << (i*2);
                        }
                        checkRows[current][working] = 0;
                }
                num++;
                for(i = 0; i < working * 2; i++)
                {
                        compare += 1 << i;
                } 
                if(num > compare)
                        return 0;
                for(current = 0; current <= working; current++)
                {
                        checkRows[(num & (3 << current*2)) >> current*2][working] += 1 << current;
                }
        } while(isRects(checkRows));
        return 1;
}

void init(int checkRows[][SIZE])
{
        int i,j;
        for(i = 0; i < SIZE; i++)
        {
                for(j = 0; j < 4; j++)
                {
                        checkRows[j][i] = 0;
                }
        }
        
        checkRows[0][0] = 1;
        checkRows[1][0] = 2;
        checkRows[2][1] = 1;
        checkRows[3][1] = 2;
}


int isRects(int checkRows[][SIZE])
{
        int a,i,j,k;
        for(j = 0; j < SIZE-1; j++)
        {
                for(k = j+1; k < SIZE; k++)
                {
                        for(i = 0; i < 4; i++)
                        {
                                a = checkRows[i][j] & checkRows[i][k];
                                if((a & (a-1)) != 0)
                                        return 1;
                        }
                }
        }
        return 0;
}

int main()
{
        int i;
        int working = 2;
        int checkRows[4][SIZE];
        int count[SIZE];

        init(checkRows);
        displayGrid(checkRows);

        do
        {
                if(!incrementCol(working,checkRows)) {
                        for(i = 0; i < working; i++)
                                checkRows[0][i] -= (1 << working);
                        working--;
                }
                
                if(incrementRow(working,checkRows)) {
                        count[working]++;
                        working++;
                }
                else {
                        for(i = 0; i < 4; i++) {
                                checkRows[i][working] = 0;
                        }
                }
                
        }
        while(working < 7);
        
        displayGrid(checkRows);


        return 0;
}