#include <stdio.h>
#include <math.h>
struct item{
  int key; int i; int j;
};
int i,n,t,k, size, F[100][100]; 
struct item X[100], Y[100], Z[100], a[100];
siftup(int p, int q, struct item a[], int flag) // flag=0 for minimum heap
{ int j,k; struct item y, z;                    // flag=1 for maximum heap
  y=a[p]; j=p; k=2*j;
  while (k<=q){z = a[k];
    if (k<q) if (flag^(z.key>a[k+1].key)){k++; z = a[k];}
    if (flag^(y.key<=z.key)) break;  // ^ is for exclusive or
    a[j] = z; j = k; k = 2*j;
  } a[j]=y; 
}
sort(int n, struct item a[])
{ int i; struct item w;
  for (i=n/2; i>=1; i--) siftup(i,n,a,1);
  for (i=n-1; i>=1; i--) {
    w = a[i+1]; a[i+1] = a[1]; a[1] = w;
    siftup(1,i,a,1);
  }
}
insert(struct item x, struct item a[]){
  int i,j; struct item y;
  size++; i=size;
  F[x.i][x.j]=1;
  while(i>=2){
    j=i/2; y=a[j];
    if(x.key>=y.key) break;
    a[i]=y; i=j;
  } a[i]=x;
}
struct item delete_min(struct item b[]){
  struct item w= b[1];
  b[1]=b[size]; size--; siftup(1, size, b, 0);
  return w;
}
int f(int i, int j){
  return F[i][j];
}
select(int n, struct item X[], struct item Y[], struct item Z[]){
  int i, j, ii, kk, size=1;
  struct item w;
  for(kk=1; kk<=k; kk++){
    a[kk]=delete_min(Z);
    i=a[kk].i; j=a[kk].j;
    printf("value= %d ", a[kk].key); getchar();
    if(f(i+1, j)==0){
    w.key=X[i+1].key + Y[j].key; w.i=i+1; w.j=j;
    insert(w, Z);
    }
    if(f(i,j+1)==0){
    w.key=X[i].key+Y[j+1].key; w.i=i; w.j=j + 1;
    insert(w, Z);
    }
    printf("size= %d w i1 i2 %d %d %d \n", size, w.key, w.i, w.j);
    for (ii=1;ii<=2*n;ii++) printf("%d %d %d | ",Z[ii].key, Z[ii].i, Z[ii].j);
    printf("\n");
  }
}
main()
{  struct item w; 
  printf("input size \n "); scanf("%d",&n); getchar();
  size=0; k=n;
  for (i=1;i<=n;i++)X[i].key=random()%21; 
  for (i=1;i<=n;i++)Y[i].key=random()%20; 
  sort(n, X); sort(n, Y); 
  for (i=1;i<=n;i++) printf("%d ", X[i].key); printf("\n");
  for (i=1;i<=n;i++) printf("%d ", Y[i].key); printf("\n");
  w.key=X[1].key+Y[1].key; w.i=1; w.j=1;
  insert(w, Z);
  for (i=1;i<=n;i++) X[i].i=i;
  for (i=1;i<=n;i++) Y[i].i=i;
  select(n, X, Y, Z);
}