#include <stdlib.h>
#include <stdio.h>

int n;
int numchunkz;
char* dibits[]  = {"00", "01", "11", "10"};
char* tribits[] = {"000", "001", "011", "010", "110", "100", "101", "111", 
   	           "111", "101", "100", "110", "010", "011", "001", "000"};

typedef struct {
  char *bitz;
  void *next;
  void *prev;
  int last;
  int index;
  int finished;
  int num;
} bitchunk;

void flip(bitchunk* chunk) 
{
  if(chunk->num == 4) {
    chunk->bitz = dibits[chunk->index];
  } else {
    chunk->bitz = tribits[chunk->index];
  }
  chunk->index = (chunk->index + 1) % chunk->num;
  if (chunk->index == 0 || chunk->index == 8) chunk->finished = 1;
}

void print(bitchunk** chunka) 
{
  bitchunk *bc = chunka[numchunkz-1];
  while(bc->prev) {
    printf("%s", bc->bitz); 
    bc = bc->prev;
  } 
  printf("%s", bc->bitz); 
  printf("\n");
}

void iterate(bitchunk** chunka, bitchunk* chunk) 
{
  while(!chunk->finished) {
    flip(chunk);
    if(chunk->last) print(chunka);
    if(chunk->next) iterate(chunka, chunk->next);
  }
  chunk->finished = 0;
}

bitchunk** calcchunks(int n) 
{
  int lo = n % 3;
  int numchunks  = n / 3;
  int numtwos = 0;

  switch(lo) {
    case(2):
      numchunks += 1;
      numtwos = 1;
    case(0):
      break;
    case(1):
      numchunks += 1;
      numtwos = 2;
      break;
  }

  int i;
  bitchunk** chunkz = (bitchunk**)malloc(sizeof(bitchunk*) * numchunks);

  for(i=0; i<numchunks; i++) { 
    chunkz[i] = (bitchunk*)malloc(sizeof(bitchunk));
    if(i <= numtwos - 1) chunkz[i]->num = 4;
    else chunkz[i]->num = 16;

    if(i > 0) chunkz[i]->prev = chunkz[i-1];
  }

  for(i=0; i< numchunks-1; i++) { 
    bitchunk *bc = chunkz[i];
    bc->next = chunkz[i+1];
  }

  chunkz[numchunks-1]->last = 1;

  numchunkz = numchunks;
  return chunkz;
} 

int main (int argc, char **argv) 
{
  if(argc != 2) {
    printf("Usage: bitchunk <numbits>\n");
    return -1;
  }
  int n = atoi(argv[1]);
  bitchunk** chunks = calcchunks(n);
  iterate(chunks, chunks[0]);
}