//This works
#include <stdio.h>
int n, a[10], next[10], pos[10], d[10], up[10], c[10];
out(){
int i;
for(i=1;i<=n;i++)printf("%d ", a[i]);
printf("\n");
}
swap(int i, int j){int w;
  w=a[i]; a[i]=a[j]; a[j]=w;
  c[i]++; if(i!=0)out();
}
update_next(int i){
    if(d[i-1]>0){
      if((a[i]>a[i-1])&&(a[i]<next[i-1]))next[i-1]=a[i];
    } else{
    if((a[i]<a[i-1])&&(a[i]>next[i-1]))next[i-1]=a[i];
    }
}
main(){int i, k;
  scanf("%d",&n); getchar();
  for(i=1;i<=n;i++)a[i]=i;
  for(i=1;i<=n;i++)up[i]=i;
  for(i=0;i<=n;i++)d[i]=1;
  for(i=0;i<=n;i++)c[i]=1;
  for(i=1;i<=n;i++)pos[i]=i;
  for(i=1;i<=n;i++)next[i]=9;
  printf("Start\n"); i=n;
  out();
  while(i!=0){
    i=up[n]; up[n]=n;
    if(d[i]>0)next[i]=9; else next[i]=0;
    update_next(i);
    if(c[i]<n-i+1)swap(i, pos[i]);
    if(c[i]==n-i+1){
      update_next(i);
      up[i]=up[i-1]; up[i-1]=i-1;
      if(next[up[i]]==a[i])pos[up[i]]=i;
      d[i]=-d[i]; c[i]=1;
    }  
  }
}