// oeis.org/A056971
// Lab 4 Spring 2018, count minHeaps
// Uses array instead of bit ops

#include <stdlib.h>
#include <stdio.h>
// For getrusage()
#include <sys/time.h>
#include <sys/resource.h>

double CPUtime()
{
struct rusage rusage;

getrusage(RUSAGE_SELF,&rusage);
return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
       + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

int increment;

int n,heap[18],count=0;
char entriesUsed[18];

void backtrack(int k) {
  int i;

  if (k==n) {
    count++;
    if (increment>0 && count%increment==0) {
      // Scan for empty leaf
      for (i=n/2+1;i<=n && entriesUsed[i];i++)
        ;
      heap[i]=n;
      printf("%d: ",count);
      for (i=1;i<=n;i++)
        printf("%d ",heap[i]);
      printf("\n");
      }
    return;
    }

  // Place k at each legal heap slot
  if (k==1) {
    heap[1]=k;
    entriesUsed[1]=1; // Turn on bit for slot 1
    backtrack(k+1);
    entriesUsed[1]=0; // Turn off bit for slot 1
    return;
    }

  //for (i=n;i>=2;i--)
  for (i=2;i<=n;i++)
    // Must have slot i open and its parent occupied
    if (!entriesUsed[i] && entriesUsed[i/2]) {
      heap[i]=k;
      entriesUsed[i]=1; // Turn on bit for slot i
      backtrack(k+1);
      entriesUsed[i]=0; // Turn off bit for slot i
      }
  }

int main() {
  double startCPU,stopCPU;
  int i;

  scanf("%d %d",&n,&increment);
  if (n<0 || n>17)
    exit(0);
  if (increment<0)
    exit(0);
  startCPU=CPUtime();
  for (i=0;i<18;i++)
    entriesUsed[i]=0;
  backtrack(1);
  stopCPU=CPUtime();
  printf("%d heaps for n=%d, CPU=%5.2f\n",count,n,stopCPU-startCPU);
  }