#include<stdio.h>
void afft(int n,int t[n])
{ int i;
  for(i=0;i<n;i++) printf("%d ",t[i]);
  printf("\n");
}
void fusion(int a,int b,int t[])
{ int u[b], i=0, j=a, k=0;
  while(i<a && j<b) u[k++]=t[t[i]<t[j]?i++:j++];
  while(i<a       ) u[k++]=t[          i++    ];
  while(       j<b) u[k++]=t[              j++];
  for(k=0;k<b;k++) t[k]=u[k];
}
void trifusion(int n,int t[])
{ int m=n/2;
  if(m)
  { trifusion(m  ,t  );
    trifusion(n-m,t+m);
    fusion(m,n,t);
  }
}
int main()
{ int n=100000, t[n], x=0, i;
  for(i=0;i<n;i++) t[i]=x=1005*x+1;
  afft(10,t);
  trifusion(n,t);
  afft(10,t);
  return 0;
}