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

#define MIN(x,y) (x>y)?y:x

#define MAX(x,y) (x>y)?x:y


unsigned int rem[296] = {
0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,
0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,
0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
0x1000000,0x2000000,0x4000000,0x8000000,0x10000000,0x20000000,0x40000000,0x80000000,
0x4c11db7,0x9823b6e,0x130476dc,0x2608edb8,0x4c11db70,0x9823b6e0,0x34867077,0x690ce0ee,
0xd219c1dc,0xa0f29e0f,0x452421a9,0x8a484352,0x10519b13,0x20a33626,0x41466c4c,0x828cd898,
0x1d8ac87,0x3b1590e,0x762b21c,0xec56438,0x1d8ac870,0x3b1590e0,0x762b21c0,0xec564380,
0xdc6d9ab7,0xbc1a28d9,0x7cf54c05,0xf9ea980a,0xf7142da3,0xeae946f1,0xd1139055,0xa6e63d1d,
0x490d678d,0x921acf1a,0x20f48383,0x41e90706,0x83d20e0c,0x36501af,0x6ca035e,0xd9406bc,
0x1b280d78,0x36501af0,0x6ca035e0,0xd9406bc0,0xb641ca37,0x684289d9,0xd08513b2,0xa5cb3ad3,
0x4f576811,0x9eaed022,0x399cbdf3,0x73397be6,0xe672f7cc,0xc824f22f,0x9488f9e9,0x2dd0ee65,
0x5ba1dcca,0xb743b994,0x6a466e9f,0xd48cdd3e,0xadd8a7cb,0x5f705221,0xbee0a442,0x79005533,
0xf200aa66,0xe0c0497b,0xc5418f41,0x8e420335,0x18451bdd,0x308a37ba,0x61146f74,0xc228dee8,
0x8090a067,0x5e05d79,0xbc0baf2,0x178175e4,0x2f02ebc8,0x5e05d790,0xbc0baf20,0x7cd643f7,
0xf9ac87ee,0xf798126b,0xebf13961,0xd3236f75,0xa287c35d,0x41ce9b0d,0x839d361a,0x3fb7183,
0x7f6e306,0xfedc60c,0x1fdb8c18,0x3fb71830,0x7f6e3060,0xfedc60c0,0xf979dc37,0xf632a5d9,
0xe8a45605,0xd589b1bd,0xafd27ecd,0x5b65e02d,0xb6cbc05a,0x69569d03,0xd2ad3a06,0xa19b69bb,
0x47f7cec1,0x8fef9d82,0x1b1e26b3,0x363c4d66,0x6c789acc,0xd8f13598,0xb5237687,0x6e87f0b9,
0xdd0fe172,0xbededf53,0x797ca311,0xf2f94622,0xe13391f3,0xc6a63e51,0x898d6115,0x17dbdf9d,
0x2fb7bf3a,0x5f6f7e74,0xbedefce8,0x797ce467,0xf2f9c8ce,0xe1328c2b,0xc6a405e1,0x89891675,
0x17d3315d,0x2fa662ba,0x5f4cc574,0xbe998ae8,0x79f20867,0xf3e410ce,0xe3093c2b,0xc2d365e1,
0x8167d675,0x60eb15d,0xc1d62ba,0x183ac574,0x30758ae8,0x60eb15d0,0xc1d62ba0,0x876d4af7,
0xa1b8859,0x143710b2,0x286e2164,0x50dc42c8,0xa1b88590,0x47b01697,0x8f602d2e,0x1a0147eb,
0x34028fd6,0x68051fac,0xd00a3f58,0xa4d56307,0x4d6bdbb9,0x9ad7b772,0x316e7353,0x62dce6a6,
0xc5b9cd4c,0x8fb2872f,0x1ba413e9,0x374827d2,0x6e904fa4,0xdd209f48,0xbe802327,0x79c15bf9,
0xf382b7f2,0xe3c47253,0xc349f911,0x8252ef95,0x64c29d,0xc9853a,0x1930a74,0x32614e8,
0x64c29d0,0xc9853a0,0x1930a740,0x32614e80,0x64c29d00,0xc9853a00,0x97cb69b7,0x2b57ced9,
0x56af9db2,0xad5f3b64,0x5e7f6b7f,0xbcfed6fe,0x7d3cb04b,0xfa796096,0xf033dc9b,0xe4a6a481,
0xcd8c54b5,0x9fd9b4dd,0x3b72740d,0x76e4e81a,0xedc9d034,0xdf52bddf,0xba646609,0x7009d1a5,
0xe013a34a,0xc4e65b23,0x8d0dabf1,0x1eda4a55,0x3db494aa,0x7b692954,0xf6d252a8,0xe965b8e7,
0xd60a6c79,0xa8d5c545,0x556a973d,0xaad52e7a,0x516b4143,0xa2d68286,0x416c18bb,0x82d83176,
0x1717f5b,0x2e2feb6,0x5c5fd6c,0xb8bfad8,0x1717f5b0,0x2e2feb60,0x5c5fd6c0,0xb8bfad80,
0x75be46b7,0xeb7c8d6e,0xd238076b,0xa0b11361,0x45a33b75,0x8b4676ea,0x124df063,0x249be0c6,
0x4937c18c,0x926f8318,0x201e1b87,0x403c370e,0x80786e1c,0x431c18f,0x863831e,0x10c7063c,
0x218e0c78,0x431c18f0,0x863831e0,0x8b17e77,0x1162fcee,0x22c5f9dc,0x458bf3b8,0x8b17e770,
0x12eed357,0x25dda6ae,0x4bbb4d5c,0x97769ab8,0x2a2c28c7,0x5458518e,0xa8b0a31c,0x55a05b8f
};

int global_gap;
int global_upper;
int global_xor_level;


//BEGIN---------------------the class xor_record--------------------------

struct xor_struct{
  unsigned int xor_value;
  unsigned char index[11];
  unsigned char count;
};

class xor_record{
 public:
  int mSize;
  int mCount;
  struct xor_struct *mpData;
  xor_record(int size);
  void add_record(unsigned int xor_value, unsigned char *depth_array, int depth);
  void sort_record();
  int search_record(unsigned int xor_value, int *pLow, int *pHigh);
  int binary_search(unsigned int xor_value, int low, int high);
};

int xor_record::binary_search(unsigned int xor_value, int low, int high)
{
  int middle;
  middle = (low+high)/2;
  if (mpData[middle].xor_value == xor_value) return middle;
  if (xor_value < mpData[middle].xor_value && middle - 1 >= low) 
    return binary_search(xor_value, low, middle-1);
  if (xor_value > mpData[middle].xor_value && middle + 1 <= high)
    return binary_search(xor_value, middle+1, high);
  return -1;
}

int xor_record::search_record(unsigned int xor_value, int *pLow, int *pHigh)
{
  int middle, low, high, i;
  middle = binary_search(xor_value, 0, mCount-1);
  if (middle < 0) return -1;
  low = middle;

  while (low-1 >=0) {
    if (mpData[low-1].xor_value == xor_value)
      low = low - 1;
    else break;
  }
  high = middle;
  while (high < mCount-1) {
    if (mpData[high+1].xor_value == xor_value)
      high = high + 1;
    else break;
  }

  *pLow = low;
  *pHigh = high;

  return 1;
}

int my_compare(const void* p1, const void* p2)
{
  struct xor_struct *l1, *l2;
  l1 = (struct xor_struct*)p1;
  l2 = (struct xor_struct*)p2;
  if (l1->xor_value < l2->xor_value) return -1;
  if (l1->xor_value > l2->xor_value) return 1;
  return 0;
}

void xor_record::add_record(unsigned int xor_value, unsigned char *depth_array, int depth)
{
  int i;
  struct xor_struct *p;
  if (mCount == mSize) {
    printf("Table too small\n");
    exit(1);
  }
  p = mpData+mCount;
  p->xor_value = xor_value;
  if (depth >= 11) {
    printf("Record too big\n");
    exit(1);
  }
  for(i=0; i<=depth; i++) 
    p->index[i] = depth_array[i];
  p->count = depth+1;
  //  printf("%u added\n", xor_value);
  mCount++;
}

void xor_record::sort_record()
{
  int i;
  printf("Start sorting\n");
  qsort((void*)mpData, mCount, sizeof(struct xor_struct), &my_compare);
  printf("Finish sorting\n");
}

xor_record::xor_record(int size)
{
  mpData = (struct xor_struct*)malloc(sizeof(xor_struct) * size);
  if (mpData == NULL) {
    printf("Insufficient Memory\n");
    exit(1);
  }
  mSize = size;
  mCount = 0;
}

//END---------------------the class xor_record--------------------------



void FillRight(xor_record *p, int upperbound, unsigned char *depth_array, int depth, unsigned int accu)
{
  int i, lowerbound;
  unsigned int my_accu;

  lowerbound = (global_xor_level == 1) ? global_gap : 1;

  for(i=upperbound; i>=lowerbound; i--) {
    depth_array[depth] = i;
    my_accu = accu ^ rem[i];
    //update the accumulater

    //calculate the upperbound for the next level
    if (depth + 1 >= global_xor_level) {
      upperbound = MIN(depth_array[depth+1 - global_xor_level]-global_gap, i-1);
    }
    else {
      upperbound = i-1;
    }

    //see if the next level is possible at all
    if (global_xor_level > depth+2) 
      FillRight(p, upperbound, depth_array, depth+1, my_accu);
    else if (global_xor_level == 1 || depth_array[depth + 2 - global_xor_level] - global_gap >= 0)
      FillRight(p, upperbound, depth_array, depth+1, my_accu);

    //    printf("%u to be added\n", my_accu);
    p->add_record(my_accu ^ 0x1, depth_array, depth);
  }
}

int CheckAnswerValidity(struct xor_struct *p, int *depth_array, int depth)
{
  int pos_left, pos_right;
  for(pos_right = 0; pos_right < global_xor_level; pos_right++) {
    pos_left = depth - (global_xor_level - pos_right - 1);
    if (pos_left < 0) continue;
    if (pos_right >= p->count) {
      if (depth_array[pos_left] - 0 < global_gap) return 0;
      break;
    }
    if (depth_array[pos_left] - p->index[pos_right] < global_gap) return 0;
  }
  return 1;
}

void PrintAnswer(struct xor_struct *p, int *depth_array, int depth)
{
  int i;
  static int poly[512];

  for(i=global_upper; i>=0; i--) 
    poly[i] = 0;
  for(i=0; i<=depth; i++) {
    poly[depth_array[i]] = 1;
    printf("%4d,", depth_array[i]);
  }
  for(i=0; i<p->count; i++) {
    poly[p->index[i]] = 1;
    printf("%4d,", p->index[i]);
  }
  printf("%4d,\n", 0);
  poly[0] = 1;

  for(i=global_upper; i>=0; i--)
    printf("%1d", poly[i]);
  printf("\n\n");
}

void CheckMatch(xor_record *p, int *depth_array, int depth, unsigned int accu)
{
  int low, high, i;
  if (p->search_record(accu, &low, &high) > 0) {
    for(i=low; i<=high; i++) {
      if (CheckAnswerValidity(p->mpData+i, depth_array, depth))
	PrintAnswer(p->mpData+i, depth_array, depth);
    }
  }
}


void Search(xor_record *p, int upperbound, int lowerbound, int *depth_array, int depth, unsigned int accu)
{
  int i;
  unsigned int my_accu;
  int low, high;


  for(i=upperbound; i>=lowerbound; i--) {
    depth_array[depth] = i;
    my_accu = accu ^ rem[i];
    //update the accumulater

    //calculate the upperbound for the next level
    if (depth + 1 >= global_xor_level) {
      upperbound = MIN(depth_array[depth+1 - global_xor_level]-global_gap, i-1);
    }
    else {
      upperbound = i-1;
    }

    Search(p, upperbound, lowerbound, depth_array, depth+1, my_accu);

    CheckMatch(p, depth_array, depth, my_accu);

  }
}


void main(int argc, char*argv[])
{
  int depth_array_left[12];
  unsigned char depth_array_right[12];

  xor_record *p;

  int middle;
  if (argc != 5) {
    printf("usage: search upper middle xor_level gap\n");
    exit(1);
  }

  global_upper = atoi(argv[1]);

  middle = atoi(argv[2]);

  global_xor_level = atoi(argv[3]);

  global_gap = atoi(argv[4]);

  p = new xor_record(50000000);
  

  FillRight(p, middle, depth_array_right, 0, 0);
  p->add_record(0x1, depth_array_right, -1);
  printf("Precompute and store %d numbers\n", p->mCount);
  p->sort_record();

  Search(p, global_upper, middle+1, depth_array_left, 0, 0);
}