#define Ra rand()%1000

#include <stdio.h>
#include <stdlib.h>


struct nod
{
	int info;
	int prioritate;
	float cheie;
	nod *left,*right;
};
nod *root;
int nr_noduri = 0;


nod* create(int info,int prioritate,float cheie);
void insert(int info,int prioritate,float cheie, nod *&subroot);
void rot_left(nod *&n);
void rot_right(nod *&n);
void echilibrare(nod *&n);
void sterge(float cheie, nod *&subroot);
void avansare(nod *&subroot, float k);
void deletes(int a, int b);
void devanseaza(nod *&subroot, float k, int d);
int acces(nod *subroot,float k);
void modify(nod *&subroot, float k, int info);
void reverse(int a, int b);
void afisare(nod *subroot);
void afisare_fisier(nod *subroot, FILE *g);
void afisare_int(FILE *g,int n);
void citeste_fisier(FILE *f, FILE *g);
void split(nod* &R, nod* &Ts, nod* &Tg, float cheie);
void join(nod* &R, nod* Ts, nod* Tg, float key);
void incrementare(nod *&subroot);


int main()
{
	FILE *f,*g;

	f = fopen("secv8.in","r");
	g = fopen("secv8.out","w+");

	
	citeste_fisier(f,g);

	fclose(f);
	fclose(g);
	return 0;
}

void join(nod* &R, nod* Ts, nod* Tg, float cheie)
{
    R = create(0,0,cheie);
    R->left = Ts;
    R->right = Tg;   
    sterge(R->cheie,R);
}

void split(nod* &R, nod* &Ts, nod* &Tg, float cheie)
{
    insert(0,1001,cheie,R);
    Ts = R->left;
    Tg = R->right;
    free(R), R = NULL;
}


void citeste_fisier(FILE *f, FILE *g)
{
	int a,b,i;
	int v1,v2;
	char ins;

	fscanf(f,"%d %d",&a,&b);

	for (i=0;i<a;i++)
	{
		fscanf(f,"\n%c",&ins);
		if ( ins == 'I' )
		{
			fscanf(f,"%d %d",&v1,&v2);
			insert(v2,Ra,v1,root);
		}
		if ( ins == 'R' )
		{
			fscanf(f,"%d %d",&v1,&v2);
			reverse(v1,v2);
		}
		if ( ins == 'A')
		{
			fscanf(f,"%d",&v1);
			afisare_int(g,acces(root,v1));
		}
		if ( ins == 'D')
		{
			fscanf(f,"%d %d",&v1,&v2);
			deletes(v1,v2);
		}
	}
	afisare_fisier(root,g);

	fseek ( g , -1 , SEEK_CUR );
    fputc ( -1 , g );
	
}

void afisare_int(FILE *g,int n)
{
	fprintf(g,"%d\n",n);
}

void afisare_fisier(nod *subroot, FILE *g)
{
	if ( subroot == 0 )
		return;

	afisare_fisier(subroot->left,g);
	fprintf(g,"%d ",subroot->info);
	afisare_fisier(subroot->right,g);


}

void afisare(nod *subroot)
{
	if ( subroot == 0 )
		return;

	afisare(subroot->left);
	printf("%d ",subroot->info);
	afisare(subroot->right);

}

void reverse(int a, int b)
{
	int i,c,j,aux;

	c = (a+b)/2;
	
	for (i=a,j=b;i<=c;i++,j--)
	{
		aux = acces(root,i);
		modify(root,i,acces(root,j));
		modify(root,j,aux);
	}

}

void modify(nod *&subroot, float k, int info)
{
	if ( subroot == 0 )
		return;
	if ( subroot->cheie == k )
		subroot->info = info;

	if ( subroot->cheie > k )
		modify(subroot->left,k,info);
	else
		modify(subroot->right,k,info);
}

int acces(nod *subroot,float k)
{
	if ( subroot == 0 )
		return -1;
	if ( subroot->cheie == k )
		return subroot->info;

	if ( subroot->cheie > k )
		acces(subroot->left,k);
	else
		acces(subroot->right,k);

}

void devanseaza(nod *&subroot, int k, int d)
{
	if ( subroot == 0 )
		return;
	if ( subroot->cheie > k )
		subroot->cheie = subroot->cheie - d;

	devanseaza(subroot->left,k,d);
	devanseaza(subroot->right,k,d);

}

void deletes(int a, int b)
{
	int i,d;

	for (i = a;i<=b;i++)
		sterge(i,root);
	d = (b-a)+1;
	devanseaza(root,b,d);
}


void sterge(float cheie, nod *&subroot)
{
	if ( subroot == 0 )
		return;
	
	if ( subroot->cheie < cheie )
		sterge(cheie,subroot->right);
	if ( subroot->cheie > cheie )
		sterge(cheie,subroot->left);

	if ( subroot->cheie == cheie )
	{
		if (( subroot->left == 0) && ( subroot->right == 0 ))
		{
			free(subroot);
			subroot = 0;
		}

		else
		{
			if (( subroot->left == 0 ) || ( subroot->right == 0 ))
			{
				if ( subroot->left == 0 )
					rot_right(subroot);
				else
					rot_left(subroot);
			}
			else
				if ( subroot->left->prioritate > subroot->right->prioritate )
					rot_left(subroot);
				else
					rot_right(subroot);
			sterge(cheie,subroot);
		}
	}
}

void echilibrare(nod *&n)
{
	if ( n->left != 0 )
		if ( n->prioritate < n->left->prioritate )
			rot_left(n);
	if ( n->right != 0 )
		if ( n->prioritate < n->right->prioritate )
			rot_right(n);

}

void rot_left(nod *&n)
{
	nod *t = n->left;

	n->left = t->right;
	t->right = n;
	n = t;
}

void rot_right(nod *&n)
{
	nod *t = n->right;

	n->right = t->left;
	t->left = n;
	n = t;
}

void avansare(nod *&subroot, float k)
{
	nod *Ts,*Td;
	k = k-0.1;

	if ( subroot == 0 )
		return;

	split(subroot,Ts,Td,k);

	incrementare(Td);
	join(subroot,Ts,Td,k);

}

void incrementare(nod *&subroot)
{
	if ( subroot == 0 )
		return;
	subroot->cheie++;
	incrementare(subroot->left);
	incrementare(subroot->right);
}

void insert(int info,int prioritate,float cheie, nod *&subroot)
{
	
	if ( subroot == 0 )
	{
		subroot = create(info,prioritate,cheie);
		nr_noduri++;
		return;
	}

	if ( subroot->cheie == cheie )
		avansare(root,cheie);
		

	if ( subroot->cheie < cheie )
		insert(info,prioritate,cheie,subroot->right);
	else
		insert(info,prioritate,cheie,subroot->left);

	
	echilibrare(subroot);
}

nod* create(int info,int prioritate,float cheie)
{
	nod *p = (nod *)malloc(sizeof(nod));
	p->info = info;
	p->prioritate = prioritate;
	p->cheie = cheie;
	p->left = 0;
	p->right = 0;
	return p;
}