#include <stdio.h>

#define IA 16807
#define IM 2147483647
#define IQ 127773
#define IR 2836
#define MASK 123459876
#define SIZE 2000

#define READ  0
#define WRITE 1

int *INPUT;
int heapsize;

long int rand0()
{
  static long int idum=1234; 
  long k;

  idum ^= MASK;
  k = idum / IQ;
  idum=IA*(idum-k*IQ)-IR*k;
  if(idum < 0) idum += IM;
  idum ^= MASK;
  return idum;
}  

long int randomnumber()
{
  return rand0() % 1000000;
}

void initializeinput()
{
  int i;
  for(i=1;i<=SIZE;i++)
    INPUT[i] = randomnumber();
}

void printref(unsigned long ref,int r_w)
{
  char hex[]="0123456789ABCDEF";
  int i;
  if(r_w==READ) printf("R"); else printf("W");
  for(i=7;i>=0;i--)
    printf("%c",hex[(ref >> i*4) & 0xF]);
  printf("\n");
}

void heapify(int node)
{
  int left = 2*node;
  int right = left + 1;
  int largest=node,temp;

  if(left<=heapsize) 
    if(INPUT[left] > INPUT[node]) largest = left; else largest = node;
  printref(left*4,READ);
  printref(node*4,READ);

  if(right<=heapsize)
    if(INPUT[right] > INPUT[largest]) largest = right;
  printref(right*4,READ);
  printref(largest*4,READ);
  
  if(largest!=node)
  {
    temp = INPUT[node];
    INPUT[node] = INPUT[largest];
    printref(node*4,WRITE);
    INPUT[largest] = temp;
    printref(largest*4,WRITE);
    heapify(largest);
  }
}  

void buildheap()
{
  int i;
  heapsize = SIZE;
  for(i=SIZE/2;i>=1;i--)
    heapify(i); 
}

void heapsort()
{
  int i,temp;
  buildheap();
  for(i=SIZE;i>=2;i--)
  {
    temp = INPUT[1];
    INPUT[1] = INPUT[i];
    INPUT[i] = temp;
    heapsize--;
    heapify(1);
  }
}

int main(int argc, char *argv[])
{
  int i;
  /* Check command line */
  if (argc !=  1)
  {
     fprintf (stderr,"Heapsort takes no command line arguments\n");
     exit(1);
  }
  INPUT = (int *) calloc(SIZE+1,sizeof(int));
  if (INPUT == NULL)
  {
    printf ("calloc failed.\n");
    exit(1);
  } 
  initializeinput();
  heapsort();
  return 0;
}