/*ΠΑΡΑΡΤΗΜΑ Β*/
/*Cartesian_tree.cpp*/
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <iostream>
# include <time.h>

struct ctnode {
int x;                    /*the x-coordinate*/
int y;                    /*the y-coordinate*/
struct ctnode *left;
struct ctnode *right;
int sympos;        /*the symmetric position of node*/
bool pointed_by_A;
};
/*during the building process of tree, we set pointed_by_A=true  if and only if the respective node* *(x,y) is pointed by A[i] such as:x<=i. When the building process is finished, every  node has been* *pointed by some position of Array A*/
ctnode *Build_cartessian_tree (int *Y,int *X,int l,int r);
/*the building routine of Cartesian tree T*/
int Build_Array_A(int U,int S);
/*We use an array A of size M which stores pointers (in position i, 1<=i<=M) to the node (x,y) of the* *tree T, such as x<=i. So, in O(1) time we can determine the two respective nodes the nearest* *common ancestor(nca) of which we must compute*/  
void nca (int u,int v,int S); 
/*the recursive nca routine that begins with node z=nca(u,v) and continues recursively with nodes nca(u,u1) and nca(u2,w),where u1=pred(z) and u2=succ(z) respectively in T(in symmetric order)*/ 
int y_min(int *Y,int l,int r);
/*This routine finds the minimum between Y[l] and Y[r] values*/
double cputime;
struct ctnode *sym,*A;
struct ctnode CT;
int *X;
int *Y;
int N,M,a,b,c,pos_min,sp=0;
clock_t start,finish,duration;
clock_t begin,overhead;
long loop;
float seconds,overhead_sec;
float t_access;

int main()
{
	int i;
	printf ("give me the size of Universal U \n");
    scanf("%d",&M);
    printf ("give me the size of S\n");
    scanf("%d",&N);
   	X=(int *)malloc(sizeof(int)*N);
	Y=(int *)malloc(sizeof(int)*N);
	
    for (i=1;i<N;i=i+1)   
	{
		printf("give me the ");
		printf("%d",i);
		printf(" ");
		printf("x_coordinate:");
		scanf("%d",&X[i]);
		printf("give me the ");
	              printf("%d",i);
	              printf(" ");
		printf("y_coordinate:");
		scanf("%d",&Y[i]);
		
	}

      for (i=1;i<N;i=i+1)
	{
	   sym=new (struct ctnode); 
	   
	}  
	Build_cartessian_tree (Y,X,1,N-1);
      /*Build_Array_A(M,N);*/
	  printf("print tree with points\n");
	  for (i=1; i<N; i++)
	  {
		  printf("(");
		  printf("%d",sym[i].x);
		  printf(",");
		  printf("%d",sym[i].y);
		  printf("),");
	  }
	  /*for (i=1; i<N; i++)
	  {
		  printf("(");
		  printf("%d",X[i]);
		  printf(",");
		  printf("%d",Y[i]);
		  printf("),");
	  }*/
	/* query=[a,b] /(-00, c] */
	  a=0;
	  b=0;
	  c=0;
	  for (i=1; i<=5;i++)
	  {
		  printf("\n");
		  printf("%d",i);
		  printf("  TEST\n");
      printf (" Give me the left bound of interval[a,b]  \n");
      scanf("%d",&a);
      printf (" Give me the right bound of interval[a,b] \n");
      scanf("%d",&b);
      printf (" Give me the upper bound of interval [-oo,c] \n");
      scanf("%d",&c);
	  loop=0;
	  duration=0;
	  begin=clock();
	  /*execute loop until duration==10 sec*/
	while (duration < 10*CLOCKS_PER_SEC)
{
      loop++;
	  /*get clock cycles before the query has been answered*/
	  start=clock();
	  nca (sym[a].sympos,sym[b].sympos,N/2);
	  /*get clock cycles after the query has been anwered*/
	  finish=clock();
	  /*add cumulatively the duration*/
	  duration+=finish-start;
}

overhead=clock()-begin-duration;
overhead_sec=(float) overhead/CLOCKS_PER_SEC;   
seconds=(float) duration / CLOCKS_PER_SEC;
t_access=(float) seconds / loop;
printf("t_access:");
printf("%f",t_access);
printf("time_overhead:");
printf("%f",overhead_sec);
printf("\n");	
	  } 
return(0);
}


int Build_Array_A(int U,int S)
{
	int k;
	int j,i;
	bool pointed=false;
	for (i=1;i<=2*S-1;i=i+1)
	{
	   A=new (struct ctnode); 
	   
	}
	pointed=false;
	printf("PRINT ARRAY A\n");
	for (k=1; k<=U;++k)
	{
		for (j=1;j<=2*S-1;j=j+1)
		
			if (k<=sym[j].x && pointed==false && sym[j].pointed_by_A==false)
			{
				A[k]=sym[j];
				printf("%d",A[k]);
				pointed=true;
                sym[j].pointed_by_A=true;
			}
		pointed=false;
	}
return(0);
}


void nca (int u, int v,int S)
{ 
	int k,d,pred,succ,nca1;
	bool itself=false;
	d=0;
	d=ceil(log(S));
	nca1=u^v;
	k=1;
	while (nca1<S)
	{
	nca1=nca1<<1;
	k=k+1;
	}
	nca1=u>>(d+1-k);
	if (nca1 % 2==0) nca1=nca1+1;
	nca1=nca1<<(d+1-k);
	if (Y[nca1]<=c && loop==1)
{
printf("(");
printf("%d",X[nca1]);
printf(",");
printf("%d",Y[nca1]);
printf("),");

}
	pred=nca1-1;
	if (u<pred) nca(u,pred,S);
	else if (u=pred) 
	{
		if (Y[u]<=c && loop==1)
		{
printf("(");
printf("%d",X[u]);
printf(",");
printf("%d",Y[u]);
printf("),");
		}
	}
	else;
    succ=nca1+1;
	if (succ<v) nca(succ,v,S);
	else if (succ=v) 
	{
if (Y[v]<=c && loop==1)
{
printf("(");
printf("%d",X[v]);
printf(",");
printf("%d",Y[v]);
printf("),");
}
	}
	else;

}
int y_min(int *Y,int l,int r)
{
	int i,ymin;
	ymin=Y[1];
	for (i=l; i<=r; i++)
	{
		if (Y[i]<=ymin) 
		{
			ymin=Y[i];
			pos_min=i;
		}
	}
	return pos_min;
}





ctnode *Build_cartessian_tree (int *Y,int *X,int l,int r)
{
int m;
m=y_min(Y,l,r); /*returns the position m of minimum value between Y[l] and Y[r]*/
		if (l<m-1) 
			Build_cartessian_tree (Y,X,l,m-1); /*construction of left subtree*/ 
		else if (l==m-1)
		{
			sp++;
		sym[sp].x=X[l];
		sym[sp].y=Y[l];
		sym[sp].sympos=sp;
		sym[sp].left=NULL;
		sym[sp].right=NULL;
		sym[sp].pointed_by_A=false;
		}
		else ;

		sp++;
		sym[sp].x=X[m]; /*construction of the root of the respective subtree*/
		sym[sp].y=Y[m];
		sym[sp].sympos=sp;
		sym[sp].pointed_by_A=false;
		if (m+1<r) Build_cartessian_tree (Y,X,m+1,r); /*construction of right subtree*/
			else if (m+1==r)
		{
		sp++;
		sym[sp].x=X[r];
		sym[sp].y=Y[r];
		sym[sp].sympos=sp;
		sym[sp].left=NULL;
		sym[sp].right=NULL;
		sym[sp].pointed_by_A=false;
		}
		else ;

	return (0);
}

Our_solution.cpp

# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <iostream>
# include <time.h>

# define micro_size 2 

/*according to input size N, we define from the begining the size of micro-buckets (the buckets of last level with loglog(N) size) in order to alocate the respective space for the respective arrays. For example in this case for the smallest set of N=16 elements, micro_size=loglogN=2*/

# define micro_answer 2

/*for the same reason as before!*/

# define universe 32
# define un 32
# define bucket_size 7
/*I define the number of nodes (nodes+leaves=2*leaves-1) of the tree which stores the logN(=4) points of the respective middle-level bucket*/
# define that_micro 9
/*It is the number_of_microbuckets+1,1<=number_of_microbuckets<=N/loglogN*/
# define max 1000
/*some big constant in order to avoid some infinite-loops in persistent lists inside*/

int *micro_array_x;
int *micro_array_y;
struct tnode {
int x; /*x-coordinate*/
int y; /*y-coordinate*/
struct tnode *left;
struct tnode *right;
int sym_pos; /*the symmetric position of the respective (x,y) node*/
int pointed_by_array_A; /*if there is a pointer from A[i] to node (x,y)
			 such as x<=i then pointed_by_array_A=1 else
			 pointed_by_array_A=0*/
int persist_list_x[universe];
int persist_list_y[universe];
 /* In the root node (x,y) we construct lists that store in y_increasing order all the points of the respective  subtree.To avoid repetitive information we construct these  lists using the method of partial persistency*/
};

int Build_tree (int *X,int *Y,int S);
/*Constructs our 1st-level tree by the method we described in our paper*/ 
int Build_tree1 (int *X,int *Y,int S,int that_subset);
/*Constructs the "that_subset" tree in 2nd level, where 1<=that_subset<=N/logN.*/
/*The construction method is the same for all the trees*/ 
int Build_Array_A2(int U,int S,struct tnode *A);
/*Array with pointers to the nodes of 1st level tree*/
int Build_Array_A1(int U,int S, struct tnode* A,int number_of_buckets);
/*Array with pointers to nodes of 2nd level trees*/
int Build_Array_A(int U,int S, int* A,int *Rep);
/*Array with pointers to representatives of last_level buckets (or microbuckets) for each of which we construct a precomputed table taking into account all the posible permutations*/
int nca (int u,int v,int S);
/*returns the symmetric value of nca(u,v) node in a balanced binary tree. Our structure is always balanced independent on input set S*/
int miny (int sympos1,int sympos2);
/*Between 2 nodes with symetric positions sympos1 and sympos2 respectively returns the symetric value of the node with the minimum y-coordinate*/ 
int miny_1 (int that_subset,int sympos1,int sympos2);
/*Between 2 nodes with symetric positions sympos1 and sympos2 respectively in the "that_subset" tree of 2nd level, where 1<=that_subset<=(N/logN),returns the symetric value of the node with the minimum y-coordinate*/ 
void quicksort(int Sy[ ],int Sx[ ], int a, int z); 
/*The classic sorting by y-coordinate routine.We also can use the mergesort algorithm since the persistent lists of the 2 sons are already sorted by y_coordinate and the processing time is better(linear).Anyway, the time is preprocessing, so, it doesn't matter*/
double cputime;
int Answer1_x[un],Answer1_y[un],Answer2_x[un],Answer2_y[un],Answer_x[un],Answer_y[un];
int Answer1_1x[un],Answer1_1y[un],Answer2_1x[un],Answer2_1y[un],Answer[un];
struct tnode Sym[universe];
/*Array of nodes of 1st level tree*/
struct tnode Sym1[universe][bucket_size];
/*Array of nodes of 2nd level tree. The 1st dimension of Sym1 array represents the tree (bucket_tree) of 2nd level we refer to and the 2nd dimension of this array represents the respective node of that tree we can have acces to.*/
int irow0,irow1,irow2,irow3,irow4,irow,icolumn,that_subset;
int level=0;
int counter=0,nca1=0;
int *Rep1_x,*Rep1_y,*Rep1_1x,*Rep1_1y,*Rep2_x,*Rep2_y;
clock_t start,finish,duration;
clock_t begin,overhead;
float seconds,overhead_sec;
float t_access;
long loop;

int main()
{
int i,a,b,c,cl,d,fores,l,w,w1,w2,k,j,N,M;
int size1,size2,that_bucket,p,pos,posy,posa,posb,posw;
 int number_of_microbuckets,number_of_buckets,count_size,count_size_in;
int *X,*X1,*X2;
int *Y,*Y1,*Y2;
int *A,*A0;
struct tnode *A1,*A2;
int Tx[universe][micro_size+2];
/*the 1st dimension represents the micro_bucket we reffer to, there are N/loglogN such micro_buckets,and the 2nd one the position we store the respective  x_coordinate*/
int Ty[universe][micro_size+2];/*the same for y_coordinate*/
int Precomp_Array_x[that_micro][micro_size+2][micro_size+2][micro_size+2][micro_answer+2];
/*The 1st dimension represents the micro_bucket we reffer to,there are N/loglogN such micro_buckets,the 2nd and 3rd dimensions represent all the posible left and right x-coordinate bounds repsectively, the 4th dimension represents the upper y_coordinate bound  and the last one (5th dimension)is  the position of the Array in which we store the x_coordinate of a point (x,y) with value_of_2nd_coordinate x  value_of_3nd_coordinate  and  y  value_of_4nd_coordinate */
 int Precomp_Array_y[that_micro][micro_size+2][micro_size+2][micro_size+2][micro_answer+2];
/*the respective Array for the point (x,y) above, where the last dimension cell stores the y_coordinate*/
bool pointed=false,getout;
bool no_answer_in_microbucket=false;

	printf ("give me the size of Universal U \n");
 scanf("%d",&M);
getchar();
 printf ("give me the size of S\n");
 scanf("%d",&N);
size1=ceil(log(log(N)));
size2=ceil(log(N))+1;
printf ("%d", size1);
printf ("%d", size2);
number_of_microbuckets=ceil(N/size1);
number_of_buckets=ceil(N/size2);
getchar();
/*printf("Give seed:");
scanf("%d",&seed);
srand(seed);*/
X=(int *)malloc(sizeof(int)*N);
Y=(int *)malloc(sizeof(int)*N);
X1=(int *)malloc(sizeof(int)*size2);
Y1=(int *)malloc(sizeof(int)*size2);
X2=(int *)malloc(sizeof(int)*number_of_buckets);
Y2=(int *)malloc(sizeof(int)*number_of_buckets);
A=(int *)malloc(sizeof(int)*M);
A0=(int *)malloc(sizeof(int)*M);
	for (i=1;i<=N+1;i++)
		A1=new (struct tnode);
	for (i=1;i<=number_of_buckets+1;i++)
		A2=new (struct tnode);

   /*for (i=1;i<=N;i=i+1)   
	{
		X[i]=i;
		printf(" %d ",X[i]);
		Y[i]=i;
		printf(" %d ",Y[i]);
		
	}*/
	for (i=1;i<=N;i=i+1)   
	{
		printf("give me the ");
		printf("%d",i);
		printf(" ");
		printf("x_coordinate:");
		scanf("%d",&X[i]);
		printf("give me the ");
		printf("%d",i);
		printf(" ");
		printf("y_coordinate:");
		scanf("%d",&Y[i]);
		
	}
		for (irow=0; irow<universe; irow++)
		 for (icolumn=0; icolumn<micro_size+2; icolumn++)
		 {Tx[irow][icolumn]=0;
		    Ty[irow][icolumn]=0;
		 }
		 for (irow0=0;irow0<that_micro;irow0++)  
		   for (irow1=0; irow1<micro_size+2; irow1++)
		    for (irow2=0; irow2<micro_size+2; irow2++)
			  for (irow3=0; irow3<micro_size+2; irow3++)
		       for (irow4=0; irow4<micro_answer+2; irow4++)
			   {Precomp_Array_x[irow0][irow1][irow2][irow3][irow4]=0;
		         Precomp_Array_y[irow0][irow1][irow2][irow3][irow4]=0;
			   }
	  /*make_microbuckets(X,Y,N);*/
	printf("make_microbuckets\n");
	k=0;
	for (i=1; i<=number_of_microbuckets; i++)
	{
	for (j=1; j<=size1; j++)
	{	Tx[i][j]=X[k*size1+j];
	    printf("%d",Tx[i][j]);
		Ty[i][j]=Y[k*size1+j];
		printf("%d",Ty[i][j]);		
	}
    k++;
	}
	printf("\n");
	printf("make_precomp_tables\n");
	printf("%d",Ty[2][1]);

	 /*make_precomp_tables(i,Tx,Ty,N);*/

	  for (d=1; d<=number_of_microbuckets; d++)
	  {
		  printf("\n");
		  printf("is the");
		  printf("%d", d);
		  printf("microbucket\n");
	   for (i=1; i<=size1-1; i++)
			
	     for (k=i+1; k<=size1; k++)
		 
		   for (j=1; j<=size1; j++)
		   {

	 	     l=1;
		   for (p=i; p<=k; p++)
			{
				if (Ty[d][p]<=Ty[d][j])
			{
			  Precomp_Array_x[d][i][k][j][l]=Tx[d][p];
			  Precomp_Array_y[d][i][k][j][l]=Ty[d][p];
			  a=Tx[d][i];
			  printf("a=");
			  printf("%d",a);

			  b=Tx[d][k];
			  printf("b=");
			  printf("%d",b);

			  cl=Ty[d][j]; 
                                             printf("c=");
			  printf("%d",cl);



			  printf("the point of answer is\n");
			  printf("x_coordinate");
			  printf("%d",Precomp_Array_x[d][i][k][j][l]);
			  printf("y_coordinate");
			  printf("%d",Precomp_Array_y[d][i][k][j][l]);
			  printf("\n");
			}
				l++;
			}
		   }
		 }
	   
		   
      /*make_rep_microbuckets(X,Y,N);*/
	  /*make_rep_buckets(X,Y,N);*/
	  i=0;
	  fores=0;
	  that_subset=1;
	  while (fores*size2<N)
	  {
		  for (i=1; i<=size2; ++i)
		  {
		      X1[i]=X[fores*size2+i];
		      Y1[i]=Y[fores*size2+i];
		  }
          Build_tree1 (X1,Y1,size2,that_subset); /*builds the 2nd level trees*/
		  printf("other_bucket_tree\n");
		  fores++;
		  that_subset++;
	  }
	  j=1;
	  for (i=1; i<=number_of_buckets; i=i+1)
	  {		
		X2[i]=X[j];
		Y2[i]=Y[j];
		j=j+size2;
	  }  
      Build_tree(X2,Y2,number_of_buckets); /*builds the 1st level tree*/ 
      /*Build_Array_A2(M,number_of_buckets,A2);*/
	  pointed=false;
	printf("1st_level tree, PRINT ARRAY2 A2\n");
	for (k=1; k<=number_of_buckets;++k)
	{
		for (j=1;j<=2*number_of_buckets-1;j=j+2)
		
			if (k<=Sym[j].x && pointed==false && Sym[j].pointed_by_array_A==0)
			{
				A2[k]=Sym[j];
				printf("%d",A2[k].sym_pos);
				pointed=true;
                Sym[j].pointed_by_array_A=1;
			}
		pointed=false;
	}
	  /*Build_Array_A1(M,size2,A1,number_of_buckets);*/
	  pointed=false;
	printf("2nd_level trees, PRINT ARRAY A1\n");
	
	that_bucket=1; 
    while (that_bucket<=number_of_buckets)
	{
	for (k=1; k<=N;++k)
	{
		for (j=1;j<=2*size2-1;j=j+2)
		{
			if (k<=Sym1[that_bucket][j].x && pointed==false &&
				Sym1[that_bucket][j].pointed_by_array_A==0)
			{
				A1[k]=Sym1[that_bucket][j];
				printf("%d",A1[k].sym_pos);
				pointed=true;
                Sym1[that_bucket][j].pointed_by_array_A=1;
			}
		}
        pointed=false;
	    if (k%size2==0) that_bucket++;
	}
	}
printf("PRINT ARRAY A\n");
	/*Build_Array_A(M,number_of_microbuckets,A,Rep1_x);*/

      pointed=false;
	  for (k=1; k<=M;++k)
	{
		for (j=1,i=1;j<=M;j=j+size1,++i)
		{


			if (k<=X[j] && pointed==false)
			{
				A[k]=i;
				pointed=true;
				printf("%d",A[k]);
			}
		}
		pointed=false;
		
	}
	  printf("PRINT ARRAY A0\n");
	  /*Build_Array_A(M,N,A0,X);*/
	 pointed=false;
	for (k=1; k<=M;++k)
	{
		for (j=1;j<=N;++j)
		{

			if (k<=X[j] && pointed==false)
			{
				A0[k]=j;
				pointed=true;
				printf("%d",A0[k]);
			}
		}
		pointed=false;
		
	}
	printf("PRINT ARRAY A\n");
	for (k=1;k<=N;k++)
	printf("%d",A[k]);
  
	printf("PRINT ARRAY A0\n");
	for (k=1;k<=N;k++)
	printf("%d",A0[k]);
    
	printf("\n");
	printf("loglogN:");
	printf ("%d", size1);
	printf("   logN:");
	printf ("%d", size2);


	  /* query=[a,b] x (-00, c] */
	  a=0;
	  b=0;
	  c=0;
	  for (i=1; i<=5;i++)
	  {
		  printf("\n");
		  printf("%d",i);
		  printf("  TEST\n");
     printf (" Give me the left bound of interval[a,b]  \n");
      scanf("%d",&a);
      printf (" Give me the right bound of interval[a,b] \n");
      scanf("%d",&b);
      printf (" Give me the upper bound of interval [-oo,c] \n");
      scanf("%d",&c);
		  
     loop=0;
	 duration=0;
	 begin=clock();
	 /*execute loop until duration==10 secs*/
	while (duration < 10*CLOCKS_PER_SEC)
{
		loop++;
		/*get clock cycles before the query has been answered*/
		start=clock();
l=1;
if (a>(A[a]-1)*size1) pos=A[a];
else pos=A[a]-1;
posa=A0[a]-(pos-1)*size1;

if (Ty[pos][size1]<=c) posy=size1;
else if (Ty[pos][size1]>=c && Ty[pos][1]<=c) posy=c;
else no_answer_in_microbucket=true;
/*We 'll retrieve answer from the left precomputed table*/
if (a==X[pos*size1] && Y[pos*size1]<=c) 
	{
    if (loop==1)
	{
	      printf("x_coordinate");
		  printf(" %d ",X[pos*size1]);
		  printf("y_coordinate");
          printf(" %d ",Y[pos*size1]);
	}
	}
    else
	{
     while (Precomp_Array_x[pos][posa][size1][posy][l]!=0 
		    && Precomp_Array_y[pos][posa][size1][posy][l]!=0 && 
			no_answer_in_microbucket==false)
{
   Answer1_x[l]=Precomp_Array_x[pos][posa][size1][posy][l];
   if (loop==1)
   {
   printf("x_coordinate");
   printf(" %d ",Answer1_x[l]);
   }
   Answer1_y[l]=Precomp_Array_y[pos][posa][size1][posy][l];
   if (loop==1)
   {
   printf("y_coordinate");
   printf(" %d ",Answer1_y[l]);
   printf("\n");
   }
   l++;
}
	}


l=1;
if (b>(A[b]-1)*size1) pos=A[b];
else pos=A[b]-1;
posb=A0[b]-(pos-1)*size1; 
if (Ty[pos][size1]<=c) posy=size1;
else if (Ty[pos][size1]>=c && Ty[pos][1]<=c) posy=c;
else no_answer_in_microbucket=true;
/*we 'll retrieve answer from the right precomputed table*/
if (b==X[(pos-1)*size1+1] && Y[(pos-1)*size1+1]<=c) 
	{
    if (loop==1)
	{
	      printf("x_coordinate");
		  printf(" %d ",X[(pos-1)*size1+1]);
		  printf("y_coordinate");
          printf(" %d ",Y[(pos-1)*size1+1]);
	}
	}
else
{	
while (Precomp_Array_x[pos][1][posb][posy][l]!=0 &&
	   Precomp_Array_y[pos][1][posb][posy][l]!=0 && 
	   no_answer_in_microbucket==false)
{
   Answer2_x[l]=Precomp_Array_x[pos][1][posb][posy][l];
   if (loop==1)
   {
      printf("x_coordinate");

   printf(" %d ",Answer2_x[l]);
   }
   Answer2_y[l]=Precomp_Array_y[pos][1][posb][posy][l];
   if (loop==1)
   {
      printf("y_coordinate");

      printf(" %d ",Answer2_y[l]);
      printf("\n");
   }

   l++;
}
}
l=2*size2-1;

w1=nca(A1[a].sym_pos,l,size2);
 /*It is the node of the left tree in 2nd level of the whole structure from which we 'll retrieve by linear scanning its persistent list the left -part of the answer*/
w2=nca(1,A1[b].sym_pos,size2); /*It is the node of the right tree in 2nd level of the whole structure from which we 'll  retrieve by linear scanning its persistent list the right -part of the answer*/

posa=int(A0[a]/size2)+1;
if (posa%2==0) posa=posa+1;

posb=int(A0[b]/size2)+1;
if (posb%2==0) posb=posb+1;

w=nca(posa,posb,number_of_buckets);
  /*It is the node of the 1st level tree of the whole structure from which we 'll retrieve by linear scanning its persistent list the remaining  part of the answer*/
 

l=1;
that_bucket=int(A0[a]/size2)+1;
count_size=1;
getout=false;
while (Sym1[that_bucket][w1].persist_list_y[l]<=c && count_size<=size2 && getout==false)
{
	Answer1_1x[l]=Sym1[that_bucket][w1].persist_list_x[l];
	if (loop==1) printf(" %d ",Answer1_1x[l]);
	Answer1_1y[l]=Sym1[that_bucket][w1].persist_list_y[l];
	if (Answer1_1y[l]>=c) getout=true;
	if (loop==1) printf(" %d ",Answer1_1y[l]);
	l++;
	count_size++;
}
l=1;
that_bucket=int(A0[b]/size2)+1;
count_size=1;
getout=false;
while (Sym1[that_bucket][w2].persist_list_y[l]<=c && count_size<=size2 && getout==false)
{
	Answer2_1x[l]=Sym1[that_bucket][w2].persist_list_x[l];
	if (loop==1) printf(" %d ",Answer2_1x[l]);
	Answer2_1y[l]=Sym1[that_bucket][w2].persist_list_y[l];
	if (Answer2_1y[l]>=c) getout=true;
	if (loop==1) printf(" %d ",Answer2_1y[l]);
	l++;
	count_size++;
}
l=1;
k=1;
j=1;
count_size=1;
getout=false;
while (Sym[w].persist_list_y[l]<=c && count_size<=number_of_buckets && getout==false)
{
	Answer[l]=Sym[w].persist_list_x[l];
	if (Sym[w].persist_list_y[l]>=c) getout=true;
	if (Answer[l]>=a && Answer[l]<=b)
	{
	posw=Answer[l];
	that_bucket=int(A0[posw]/size2)+1;
count_size_in=1;
if (that_bucket>0)
{
	  while (Sym1[that_bucket][size2].persist_list_y[k]<=c && count_size_in<=size2 
		     && getout==false)
	  {
		  Answer_x[j]=Sym1[that_bucket][size2].persist_list_x[k];
		  if (loop==1) printf(" %d ",Answer_x[j]);
	      Answer_y[j]=Sym1[that_bucket][size2].persist_list_y[k];
		  if (loop==1) printf(" %d ",Answer_y[j]);
		  k++;
		  j++;
		  count_size_in++;
	  }
}
	}
	  k=1;
	  l++;
	  count_size++;
}
/*get clock cycles after the query has been answered*/
finish=clock();
/*add cumulatively the duration*/
duration+=finish-start;
}
overhead=clock()-begin-duration;
overhead_sec=(float) overhead / CLOCKS_PER_SEC;
seconds=(float) duration / CLOCKS_PER_SEC;
t_access=(float) seconds/loop;
printf("t_access:");
printf("%f",t_access);
}	 
return(0);
}

int Build_tree (int *X,int *Y,int S)
{
int k,m,i,fores,subset,buble_y,z;
fores=1;
subset=buble_y=0;
z=0;
m=0;
k=1;
i=0;
  Sym[int(pow(2,m))].x=X[k];
  Sym[int(pow(2,m))].y=Y[k];
  Sym[int(pow(2,m))].left=NULL ;
  Sym[int(pow(2,m))].right=NULL;
  Sym[int(pow(2,m))].pointed_by_array_A=0;
  Sym[int(pow(2,m))].sym_pos=int (pow(2,m));
  Sym[int(pow(2,m))].persist_list_x[1]=X[k];
  /*Sym[int(pow(2,m))].persist_list_x[2]=max;*/
  Sym[int(pow(2,m))].persist_list_y[1]=Y[k];
  /*Sym[int(pow(2,m))].persist_list_y[2]=max;*/
  printf("%d",Sym[int(pow(2,m))].sym_pos);
  printf("(");  
  printf("x:");
  printf("%d",Sym[int(pow(2,m))].persist_list_x[1]);
  printf("y:");
  printf("%d",Sym[int(pow(2,m))].persist_list_y[1]);
  printf(")");



  for (i=int (pow(2,m)); i+int (pow(2,m+1))<=2*S-1; i=i+int (pow(2,m+1)))
  {       
k=k+1;
Sym[i+int (pow(2,m+1))].x=X[k];
Sym[i+int (pow(2,m+1))].y=Y[k];
Sym[i+int (pow(2,m+1))].left=NULL;
Sym[i+int (pow(2,m+1))].right=NULL;
Sym[i+int (pow(2,m+1))].pointed_by_array_A=0;
Sym[i+int (pow(2,m+1))].sym_pos=i+int (pow(2,m+1));
Sym[i+int (pow(2,m+1))].persist_list_x[1]=X[k];
/*Sym[i+int (pow(2,m+1))].persist_list_x[2]=max;*/
Sym[i+int (pow(2,m+1))].persist_list_y[1]=Y[k];
/*Sym[i+int (pow(2,m+1))].persist_list_y[2]=max;*/
printf("%d",Sym[i+int (pow(2,m+1))].sym_pos);
printf("(");      
printf("x:");
    printf("%d",Sym[i+int (pow(2,m+1))].persist_list_x[1]);
    printf("y:");
    printf("%d",Sym[i+int (pow(2,m+1))].persist_list_y[1]);
    printf(")");  
  }  
for (m=1;m<=int(log(S)/log(2));m=m+1)
{
buble_y=miny(int(pow(2,m))-int (pow(2,m-1)),int (pow(2,m))+int (pow(2,m-1)));
Sym[int (pow(2,m))].y=Sym[buble_y].y;
Sym[int (pow(2,m))].left=&Sym[int (pow(2,m))-int (pow(2,m-1))];
Sym[int (pow(2,m))].right=&Sym[int (pow(2,m))+ int (pow(2,m-1))];
Sym[int (pow(2,m))].x=Sym[buble_y].x;
Sym[int (pow(2,m))].pointed_by_array_A=0;
Sym[int (pow(2,m))].sym_pos=int (pow(2,m));
printf("%d",Sym[int (pow(2,m))].sym_pos);


for (i=1;i<=int(S/pow(2,int(log(S)/log(2))-m));i=i+1)
	{
	   Sym[int (pow(2,m))].persist_list_x[i]=X[i];
  /*if (i=int(S/pow(2,int(log(S)/log(2))-m))) Sym[int (pow(2,m))].persist_list_x[i+1]=max;*/
	   printf("(");
	   printf("x:");
                 printf("%d",Sym[int (pow(2,m))].persist_list_x[i]);
	   Sym[int (pow(2,m))].persist_list_y[i]=Y[i];
 /*if (i=int(S/pow(2,int(log(S)/log(2))-m))) Sym[int (pow(2,m))].persist_list_y[i+1]=max;*/
	   printf("y:");
                 printf("%d",Sym[int (pow(2,m))].persist_list_y[i]);
	   printf(")");

	} 
quicksort(Sym[int (pow(2,m))].persist_list_y,Sym[int (pow(2,m))].persist_list_x,
		  1,ceil(S/pow(2,int(log(S)/log(2))-m)));
if (m<int(log(S)/log(2)))
{
	subset=int(S/pow(2,int(log(S)/log(2))-m));
 for (i=int (pow(2,m)); i+int (pow(2,m+1))<2*S; i=i+int (pow(2,m+1)))
   {
	 Sym[i+int (pow(2,m+1))].sym_pos=i+int (pow(2,m+1));
	 printf("%d",Sym[i+int (pow(2,m+1))].sym_pos);
	 for (z=1;z<=S/pow(2,int(log(S)/log(2))-m);z=z+1)
	{
	   Sym[i+int (pow(2,m+1))].persist_list_x[z]=X[fores*subset+z];
 /*if (z=S/pow(2,int(log(S)/log(2))-m)) Sym[i+int (pow(2,m+1))].persist_list_x[z+1]=max;*/

	   printf("(");
	   printf("x:");
                 printf("%d",Sym[i+int (pow(2,m+1))].persist_list_x[z]);
	   Sym[i+int (pow(2,m+1))].persist_list_y[z]=Y[fores*subset+z];
 /*if (z=S/pow(2,int(log(S)/log(2))-m)) Sym[i+int (pow(2,m+1))].persist_list_y[z+1]=max;*/

       printf("y:");
       printf("%d",Sym[i+int (pow(2,m+1))].persist_list_y[z]);
	   printf(")");
	} 
quicksort(Sym[i+int (pow(2,m+1))].persist_list_y,Sym[i+int (pow(2,m+1))].persist_list_x,1,
		  int(S/pow(2,int(log(S)/log(2))-m)));
buble_y=miny(i+int (pow(2,m+1))-int (pow(2,m-1)),i+int (pow(2,m+1))+int (pow(2,m-1)));
Sym[i+int (pow(2,m+1))].y=Sym[buble_y].y;
Sym[i+int (pow(2,m+1))].left=&Sym[i+int (pow(2,m+1))-int (pow(2,m-1))];
Sym[i+int (pow(2,m+1))].right=&Sym[i+int (pow(2,m+1))+int (pow(2,m-1))];
Sym[i+int (pow(2,m+1))].x=Sym[buble_y].x;
Sym[i+int (pow(2,m+1))].pointed_by_array_A=0;
fores=fores+1;
}
}
}
return(0);
}  

int Build_tree1 (int *X,int *Y,int S,int that_subset)
{
int k,m,i,fores,subset,z,buble_y;
fores=1;
subset=0;
z=0;
m=0;
k=1;
i=0;

  Sym1[that_subset][int(pow(2,m))].x=X[k];
  Sym1[that_subset][int(pow(2,m))].y=Y[k];
  Sym1[that_subset][int(pow(2,m))].left=NULL ;
  Sym1[that_subset][int(pow(2,m))].right=NULL;
  Sym1[that_subset][int(pow(2,m))].pointed_by_array_A=0;
  Sym1[that_subset][int(pow(2,m))].sym_pos=int (pow(2,m));
  Sym1[that_subset][int(pow(2,m))].persist_list_x[1]=X[k];
  /*Sym1[that_subset][int(pow(2,m))].persist_list_x[2]=max;*/
  Sym1[that_subset][int(pow(2,m))].persist_list_y[1]=Y[k];
  /*Sym1[that_subset][int(pow(2,m))].persist_list_y[2]=max;*/
  printf("%d",Sym1[that_subset][int(pow(2,m))].sym_pos);
  printf("(");  
  printf("x:");
    printf("%d",Sym1[that_subset][int(pow(2,m))].persist_list_x[1]);
	printf("y:");
    printf("%d",Sym1[that_subset][int(pow(2,m))].persist_list_y[1]);
	printf(")");
  for (i=int (pow(2,m)); i+int (pow(2,m+1))<=2*S-1; i=i+int (pow(2,m+1)))
  {  
k=k+1;
Sym1[that_subset][i+int (pow(2,m+1))].x=X[k];
Sym1[that_subset][i+int (pow(2,m+1))].y=Y[k];
Sym1[that_subset][i+int (pow(2,m+1))].left=NULL;
Sym1[that_subset][i+int (pow(2,m+1))].right=NULL;
Sym1[that_subset][i+int (pow(2,m+1))].pointed_by_array_A=0;
Sym1[that_subset][i+int (pow(2,m+1))].sym_pos=i+int (pow(2,m+1));
Sym1[that_subset][i+int (pow(2,m+1))].persist_list_x[1]=X[k];
/*Sym1[that_subset][i+int (pow(2,m+1))].persist_list_x[2]=max;*/
Sym1[that_subset][i+int (pow(2,m+1))].persist_list_y[1]=Y[k];
/*Sym1[that_subset][i+int (pow(2,m+1))].persist_list_y[2]=max;*/
printf("%d",Sym1[that_subset][i+int (pow(2,m+1))].sym_pos);
printf("(");  
  printf("x:");
    printf("%d",Sym1[that_subset][i+int (pow(2,m+1))].persist_list_x[1]);
	printf("y:");
    printf("%d",Sym1[that_subset][i+int (pow(2,m+1))].persist_list_y[1]);
	printf(")");
  }  
for (m=1;m<=int(log(S)/log(2));m=m+1)
{
buble_y=miny_1(that_subset,int(pow(2,m))-int (pow(2,m-1)),int (pow(2,m))+int (pow(2,m-1)));
Sym1[that_subset][int (pow(2,m))].y=Sym1[that_subset][buble_y].y;
Sym1[that_subset][int (pow(2,m))].left=&Sym1[that_subset][int (pow(2,m))-int (pow(2,m-1))];
Sym1[that_subset][int (pow(2,m))].right=&Sym1[that_subset][int (pow(2,m))+ int (pow(2,m-1))];
Sym1[that_subset][int (pow(2,m))].x=Sym1[that_subset][buble_y].x;
Sym1[that_subset][int (pow(2,m))].pointed_by_array_A=0;
Sym1[that_subset][int (pow(2,m))].sym_pos=int (pow(2,m));
printf("%d",Sym1[that_subset][int (pow(2,m))].sym_pos);
for (i=1;i<=int(S/pow(2,int(log(S)/log(2))-m));i=i+1)
	{
	   Sym1[that_subset][int (pow(2,m))].persist_list_x[i]=X[i];
	   /*if (i=int(S/pow(2,int(log(S)/log(2))-m))) 
		   Sym1[that_subset][int (pow(2,m))].persist_list_x[i+1]=max;*/

	   printf("(");
	   printf("x:");
                 printf("%d",Sym1[that_subset][int (pow(2,m))].persist_list_x[i]);
	   Sym1[that_subset][int (pow(2,m))].persist_list_y[i]=Y[i];
	   /*if (i=int(S/pow(2,int(log(S)/log(2))-m))) 
		   Sym1[that_subset][int (pow(2,m))].persist_list_y[i+1]=max;*/

	   printf("y:");
                 printf("%d",Sym1[that_subset][int (pow(2,m))].persist_list_y[i]);
	   printf(")");
	} 
quicksort(Sym1[that_subset][int (pow(2,m))].persist_list_y,
		  Sym1[that_subset][int (pow(2,m))].persist_list_x,1,
		  int(S/pow(2,int(log(S)/log(2))-m)));

if (m<int(log(S)/log(2)))
{
	subset=int(S/pow(2,int(log(S)/log(2))-m));
 for (i=int (pow(2,m)); i+int (pow(2,m+1))<2*S; i=i+int (pow(2,m+1)))
   {
	 Sym1[that_subset][i+int (pow(2,m+1))].sym_pos=i+int (pow(2,m+1));
               printf("%d",Sym1[that_subset][i+int (pow(2,m+1))].sym_pos);
	 for (z=1;z<=int(S/pow(2,int(log(S)/log(2))-m));z=z+1)
	{
	   Sym1[that_subset][i+int (pow(2,m+1))].persist_list_x[z]=X[fores*subset+z];
	   /*if (z=int(S/pow(2,int(log(S)/log(2))-m)))
		   Sym1[that_subset][i+int (pow(2,m+1))].persist_list_x[z+1]=max;*/

	   printf("(");
	   printf("x:");
                  printf("%d",Sym1[that_subset][i+int (pow(2,m+1))].persist_list_x[z]);
	   Sym1[that_subset][i+int (pow(2,m+1))].persist_list_y[z]=Y[fores*subset+z];
	   /*if (z=int(S/pow(2,int(log(S)/log(2))-m)))
		   Sym1[that_subset][i+int (pow(2,m+1))].persist_list_y[z+1]=max;*/

	   printf("y:");
                 printf("%d",Sym1[that_subset][i+int (pow(2,m+1))].persist_list_y[z]);
	   printf(")");
	} 

quicksort(Sym1[that_subset][i+int (pow(2,m+1))].persist_list_y,
		  Sym1[that_subset][i+int (pow(2,m+1))].persist_list_x,1,
		  int(S/pow(2,int(log(S)/log(2))-m)));
buble_y=miny_1(that_subset,i+int (pow(2,m+1))-int (pow(2,m-1)),
			   i+int (pow(2,m+1))+int (pow(2,m-1)));
Sym1[that_subset][i+int (pow(2,m+1))].y=Sym1[that_subset][buble_y].y;
Sym1[that_subset][i+int (pow(2,m+1))].left=
&Sym1[that_subset][i+int (pow(2,m+1))-int (pow(2,m-1))];
Sym1[that_subset][i+int (pow(2,m+1))].right=
&Sym1[that_subset][i+int (pow(2,m+1))+int (pow(2,m-1))];
Sym1[that_subset][i+int (pow(2,m+1))].x=Sym1[that_subset][buble_y].x;
Sym1[that_subset][i+int (pow(2,m+1))].pointed_by_array_A=0;
fores=fores+1;
}
}
}
return(0);
}  
int Build_Array_A2(int U,int S, struct tnode* A)
{
	int k;
	int j,i;
	bool pointed=false;
	for (i=1;i<=2*S-1;i=i+1)
	{
	   A=new (struct tnode); 
	   
	}
	pointed=false;
	printf("1st_level tree, PRINT ARRAY2 A2\n");
	for (k=1; k<=U;++k)
	{
		for (j=1;j<=2*S-1;j=j+2)
		
			if (k<=Sym[j].x && pointed==false && Sym[j].pointed_by_array_A==0)
			{
				A[k]=Sym[j];
				printf("%d",A[k]);
				pointed=true;
                Sym[j].pointed_by_array_A=1;
			}
		pointed=false;
	}
return(0);
}

int Build_Array_A1(int U,int S, struct tnode* A,int number_of_buckets)
{
	int k,that_bucket;
	int j,i;
	bool pointed=false;
	for (i=1;i<=S;i=i+1)
	{
	   A=new (struct tnode); 
	   
	}
	pointed=false;
	printf("2nd_level trees, PRINT ARRAY A1\n");
	for (that_bucket=1; that_bucket<=number_of_buckets;that_bucket++) 
	{
	for (k=1; k<=U;++k)
	{
		for (j=1;j<=2*S-1;j=j+2)
		{
			if (k<=Sym1[that_bucket][j].x && pointed==false &&
				Sym1[that_bucket][j].pointed_by_array_A==0)
			{
				A[k]=Sym1[that_bucket][j];
				printf("%d",A[k].sym_pos);
				pointed=true;
                Sym1[that_bucket][j].pointed_by_array_A=1;
			}
		}
        pointed=false;
	}
	}
return(0);
}
int Build_Array_A(int U,int S, int* A,int *Rep)
{
	int k;
	int j;
	bool pointed=false;
	for (k=1; k<=U;++k)
	{
		for (j=1;j<=S;++j)
		{

			if (k<=Rep[j] && pointed==false)
			{
				A[k]=j;
				pointed=true;
				printf("%d",A[k]);
			}
		}
		pointed=false;
		
	}
return(0);
}
int nca (int u, int v,int S)
{ 
	int k,d;
	d=0;
	d=ceil(log(S));
	nca1=u^v;
	k=1;
	while (nca1<S)
	{
	nca1=nca1<<1;
	k=k+1;
	}
	nca1=u>>(d+1-k);
	if (nca1 % 2==0) nca1=nca1+1;
	nca1=nca1<<(d+1-k);
	return(nca1);
}
int miny (int sympos1,int sympos2)
{

	if (Sym[sympos1].y<Sym[sympos2].y)
		return(sympos1);
	else return (sympos2);
}
int miny_1 (int that_subset,int sympos1,int sympos2)
{
	if (Sym1[that_subset][sympos1].y<Sym1[that_subset][sympos2].y)
		return(sympos1);
	else return (sympos2);
}

void quicksort(int Sy[],int Sx[], int a, int z)
{
	int i,k,o,y,x;
	level++;
	i = a;
	k = z+1;
	o = Sy[a];
	while(i<k)
	{
		do 
		{
			counter++;
			i++;
		}while(Sy[i]<o);
		do
		{
			counter++;
			k--;
		}while(Sy[k]>o);
		if (k>i)
		{
			y = Sy[k];
			x=Sx[k];
			Sy[k] = Sy[i];
			Sx[k] = Sx[i];
			Sy[i] = y;
			Sx[i] = x;
		}
	}
	y = Sy[a];
	x = Sx[a];
	Sy[a] = Sy[k];
	Sx[a] = Sx[k];
	Sy[k] = y;
	Sx[k] = x;
	if (a<(k-1))
		quicksort(Sy,Sx,a,k-1);
	if ((k+1)<z)
		quicksort(Sy,Sx,k+1,z);
}
