// oeis.org/A056971
// Lab 4 Spring 2018, count minHeaps

#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],entriesUsed=0,count=0;

void backtrack(int k) {
  int i;

  if (k==n) {
    count++;
    if (increment>0 && count%increment==0) {
      for (i=n/2+1;i<=n && (entriesUsed & (1<<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=entriesUsed|(1<<k); // Turn on bit for slot 1
    backtrack(k+1);
    entriesUsed=entriesUsed^(1<<k); // 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 & (1<<i)) && (entriesUsed & (1<<(i/2)))) {
      heap[i]=k;
      entriesUsed=entriesUsed|(1<<i); // Turn on bit for slot i
      backtrack(k+1);
      entriesUsed=entriesUsed^(1<<i); // Turn off bit for slot i
      }
  }

int main() {
  double startCPU,stopCPU;

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