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

typedef struct pkt pkt;

struct pkt {
	int klucz, waga, pod, height;
	char dane[30];
	pkt * parent;
	pkt * left, * right;
};

pkt * root; 

void ins (int , char *);
void del(int);

inline int max (int, int);

pkt * search(pkt *, int);
void balance(pkt *);
void LL(pkt *,pkt *,pkt *);
void LD(pkt *,pkt *,pkt *);
void RR(pkt *,pkt *,pkt *);
void RD(pkt *,pkt *,pkt *);
int zief;

pkt * H (pkt *, int);
int G(pkt *, int);
void validiate(pkt *);

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("all-small.in","r",stdin);
	//freopen("out.txt", "w", stdout);
	#endif

	char cmd, danee[30], terminate, linia[100];
	int klucz, order, adsf, n;
	pkt * tmp, * tmp2;

	while(1) {
		gets(linia);
		if (linia[0] == 'I')
			sscanf(linia, "%*c %d %s", &klucz, danee);
		else
			sscanf(linia, "%*c %d", &klucz);
		if (feof(stdin)!=0) break;			
		zief++;
		if (linia[0] == 'I') {
			ins(klucz , danee);
			//validiate(root);
		} else
		if (linia[0] == 'D') {
			del(klucz);
		} else 
		if (linia[0] == 'S') {
				tmp = search(root, klucz);
				if (tmp) {
					printf("%d %s\n", tmp->klucz, tmp->dane);
				} else 
					printf("-\n");
		} else 
		if (linia[0] == 'N') {
			adsf = G(root, klucz);
			if (adsf) {
				tmp = H(root, adsf+1);
				if (tmp)
					printf("%d %s\n", tmp->klucz, tmp->dane);
				else
					printf("-\n");
			} else {
				printf("-\n");
			}
		} else
		if (linia[0] == 'P') { 
			adsf = G(root, klucz);
			if (adsf) {
				tmp = H(root, adsf-1);
				if (tmp)
					printf("%d %s\n", tmp->klucz, tmp->dane);
				else
					printf("-\n");
			} else {
					printf("-\n");
			}
		} else
		if (linia[0] == 'G') {
			adsf = G(root, klucz);
			if (adsf)
				printf("%d\n", adsf);
			else
				printf("-\n");
		} else
		if (linia[0] == 'H') {
			tmp = H(root, klucz);
			if (tmp)
				printf("%d %s\n", tmp->klucz, tmp->dane);
			else
				printf("-\n");
		}
	}
	return 0;
}

void ins (int id, char * danea) { 
	int n;
	pkt * tmp, **tmp2;
	if (!root) {
		root = (pkt*)malloc(sizeof(pkt));
		n = 0;
		while(danea[n]!=0) {root->dane[n] = danea[n]; n++;} root->dane[n]=0;
		
		root->klucz = id;
		root->parent = 0;
		root->left = 0;
		root->right = 0;
		root->pod = 0; 
		root->height = 1;
	} else {
		tmp = root;
		while (1) {
			if (tmp->klucz == id) {
				return;
			}
			if (tmp->klucz > id) {
				if (tmp->left == NULL) {
					tmp2 = &tmp->left;
					break;
				}
				tmp = tmp->left;
			} else {			 
				if (tmp->right == NULL) {
					tmp2 = &tmp->right;
					break;
				}
				tmp = tmp->right;
			}
		}
		(*tmp2) = (pkt*)malloc(sizeof(pkt)); 
		
		n = 0; while(danea[n]!=0) {(*tmp2)->dane[n] = danea[n]; n++;} (*tmp2)->dane[n]=0; 

		(*tmp2)->klucz = id;
		(*tmp2)->parent = tmp;
		(*tmp2)->left = 0;
		(*tmp2)->right = 0;
		(*tmp2)->pod = 0;
		(*tmp2)->height = 1;

		tmp = (*tmp2)->parent;
		while(tmp) {
			tmp->pod = 0;
			if (tmp->right) tmp->pod +=(tmp->right)->pod+1;
			if (tmp->left) tmp->pod +=(tmp->left)->pod+1;

			tmp = tmp->parent;
		}		

		tmp = (*tmp2)->parent;
		while (tmp) {
			tmp->height = max(((tmp->left) ? (tmp->left)->height : 0 ) , ((tmp->right) ? (tmp->right)->height : 0 ))+1;
			n = abs( ((tmp->left) ? (tmp->left)->height : 0 ) - ((tmp->right) ? (tmp->right)->height : 0 ));
			if ( (n&1)==0) {
				balance(tmp);
				break; 
			}
			tmp = tmp->parent;
		}

	}
}

void del (int id) {
	pkt * tmp, * tmp2=0, * tmp3, * tmp4;
	pkt ** strona;
	pkt * parent;
	int n;
	if (!root) return;

	tmp = search(root, id);
	if (tmp) {
		parent = tmp->parent;
		if (tmp!=root) {
			if ((tmp->parent)->left == tmp)
				strona = &(tmp->parent)->left;
			else
				strona = &(tmp->parent)->right; 
		} else strona = 0; 


		if (tmp->left == 0 && tmp->right == 0) {
			if (strona) {
				*strona = 0;
			} else {
				root = 0;
			}
			tmp3 = tmp->parent;
		}
		else if (tmp->left == 0) {
			if (strona) { 
				*strona = tmp->right; 
			} else {
				root = tmp->right;
			}
			(tmp->right)->parent = tmp->parent;

			tmp3 = tmp->parent;

		

		} else if (tmp->right == 0) { 
			if (strona) { 
				*strona = tmp->left; 
			} else
				root = tmp->left;
			(tmp->left)->parent = tmp->parent;

			tmp3 = tmp->parent;

			

		} else { 
			
			if ((tmp->right)->left) {
				
				tmp2 = tmp->right;
				while(tmp2->left) {
					tmp2 = tmp2->left;
				}

				if (tmp2->right) {
					(tmp2->right)->parent = tmp2->parent;
					(tmp2->parent)->left = tmp2->right;
				} else {
					
					(tmp2->parent)->left = 0;
					
				}
				tmp3 = tmp2->parent; 

				if (!strona) root = tmp2;
				tmp2->parent = tmp->parent; 
				if (strona) *strona = tmp2;

				tmp2->left = tmp->left; 
				(tmp2->left)->parent = tmp2;

				tmp2->right = tmp->right;
				(tmp2->right)->parent = tmp2; 

		
			} else {
				tmp2 = tmp->right;
				tmp3 = tmp2;

				tmp2->parent = tmp->parent;
				*strona = tmp2;
				
				tmp2->left = tmp->left;
				(tmp2->left)->parent = tmp2;
				
				tmp2->height = max(((tmp2->left) ? (tmp2->left)->height : 0 ) , ((tmp2->right) ? (tmp2->right)->height : 0 ))+1;
				tmp2->pod = ((tmp2->left) ? tmp2->left->pod+1 : 0) + ((tmp2->right) ? tmp2->right->pod+1 : 0);
				

			}
		}
		
		tmp = tmp3;
		while(tmp) {
			tmp->pod = ((tmp->left) ? tmp->left->pod+1 : 0) + ((tmp->right) ? tmp->right->pod+1 : 0);
			tmp = tmp->parent;
		}		
		while(tmp3) {
			tmp3->height = max(((tmp3->left) ? (tmp3->left)->height : 0 ) , ((tmp3->right) ? (tmp3->right)->height : 0 ))+1;
			n = abs( ((tmp3->left) ? (tmp3->left)->height : 0 ) - ((tmp3->right) ? (tmp3->right)->height : 0 ) );
			if ( (abs( ((tmp3->left) ? (tmp3->left)->height : 0 ) - ((tmp3->right) ? (tmp3->right)->height : 0 ) )&1)==1) {
				break; 
			} else {
				tmp4 = tmp3->parent;
				if (n!=0) {
					balance(tmp3);
				}
				tmp3 = tmp4;
			}
		}
		if (tmp2) {
			tmp2->height = max(((tmp2->left) ? (tmp2->left)->height : 0 ) , ((tmp2->right) ? (tmp2->right)->height : 0 ))+1;
			tmp2->pod = ((tmp2->left) ? tmp2->left->pod+1 : 0) + ((tmp2->right) ? tmp2->right->pod+1 : 0);
		}

		free(tmp);
	}

}

pkt * search(pkt * tmp, int id) {
	if (tmp==0 || tmp->klucz == id) return tmp;
	if (tmp->klucz > id)
		return search(tmp->left, id);
	else return search(tmp->right, id);
	
}

void balance (pkt * a) { 

	pkt * b, * c;
	int tmp;
	tmp = ((a->right) ? (a->right)->height : 0 ) - ((a->left) ? (a->left)->height : 0 );

	if (tmp == 2) {
		b = a->right;
		tmp = ((b->right) ? (b->right)->height : 0 ) - ((b->left) ? (b->left)->height : 0 );
		if (tmp == -1) { 
			c = b->left;
			LD(a,b,c);
		} else { 
			c = b->right;
			LL(a,b,c);
		}
	} else if (tmp == -2) {
		b = a->left;
		tmp = ((b->right) ? (b->right)->height : 0 ) - ((b->left) ? (b->left)->height : 0 );
		if (tmp == -1 || tmp == 0) { 
			c = b->left;
			RR(a,b,c);
		} else { 
			c = b->right;
			RD(a,b,c);
		}
	}
}
void LL(pkt * a, pkt * b, pkt * c) {

	a->right = b->left;
	if (b->left) {
		(b->left)->parent = a;
	}

	if (!a->parent) root = b;
	b->parent = a->parent;
	if (a->parent) {
		if ((a->parent)->left == a) (a->parent)->left = b;
		else (a->parent)->right = b;
	}

	b->left = a;
	a->parent = b;

	a->height = max(((a->left) ? (a->left)->height : 0 ) , ((a->right) ? (a->right)->height : 0 ))+1;
	c->height = max(((c->left) ? (c->left)->height : 0 ) , ((c->right) ? (c->right)->height : 0 ))+1;
	b->height = max(((b->left) ? (b->left)->height : 0 ) , ((b->right) ? (b->right)->height : 0 ))+1;

	a->pod = 0;
	if (a->right) a->pod += (a->right)->pod+1;
	if (a->left) a->pod += (a->left)->pod+1;
	
	b->pod = 0;
	if (b->right) b->pod += (b->right)->pod+1;
	if (b->left) b->pod += (b->left)->pod+1;

	c->pod = 0;
	if (c->right) c->pod += (c->right)->pod+1;
	if (c->left) c->pod += (c->left)->pod+1;

}
void RR(pkt * a, pkt * b, pkt * c) {
	a->left = b->right;
	if (b->right) (b->right)->parent = a;

	if (!a->parent) root = b;
	b->parent = a->parent;
	if (a->parent) {
		if ((a->parent)->left == a) (a->parent)->left = b;
		else (a->parent)->right = b;
	}
	b->right = a;
	a->parent = b;

	a->height = max(((a->left) ? (a->left)->height : 0 ) , ((a->right) ? (a->right)->height : 0 ))+1;
	c->height = max(((c->left) ? (c->left)->height : 0 ) , ((c->right) ? (c->right)->height : 0 ))+1;
	b->height = max(((b->left) ? (b->left)->height : 0 ) , ((b->right) ? (b->right)->height : 0 ))+1;

	a->pod = 0;
	if (a->right) a->pod += (a->right)->pod+1;
	if (a->left) a->pod += (a->left)->pod+1;
	
	b->pod = 0;
	if (b->right) b->pod += (b->right)->pod+1;
	if (b->left) b->pod += (b->left)->pod+1;

	c->pod = 0;
	if (c->right) c->pod += (c->right)->pod+1;
	if (c->left) c->pod += (c->left)->pod+1;

}
void LD(pkt * a, pkt * b, pkt * c) {
	a->right = c;
	c->parent = a;

	b->left = c->right;
	if (c->right) (c->right)->parent = b;

	c->right = b;
	b->parent = c;
	a->right = c->left;
	if (c->left)(c->left)->parent = a;
	
	if (!a->parent) root = c; 
	c->parent = a->parent;
	if (a->parent) {
		if ((a->parent)->left == a) (c->parent)->left = c;
		else (c->parent)->right = c;
	}
	c->left = a;
	a->parent = c;

	a->height = max(((a->left) ? (a->left)->height : 0 ) , ((a->right) ? (a->right)->height : 0 ))+1;
	b->height = max(((b->left) ? (b->left)->height : 0 ) , ((b->right) ? (b->right)->height : 0 ))+1;
	c->height = max(((c->left) ? (c->left)->height : 0 ) , ((c->right) ? (c->right)->height : 0 ))+1;

	a->pod = 0;
	if (a->right) a->pod += (a->right)->pod+1;
	if (a->left) a->pod += (a->left)->pod+1;
	
	b->pod = 0;
	if (b->right) b->pod += (b->right)->pod+1;
	if (b->left) b->pod += (b->left)->pod+1;

	c->pod = 0;
	if (c->right) c->pod += (c->right)->pod+1;
	if (c->left) c->pod += (c->left)->pod+1;

}
void RD(pkt * a, pkt * b, pkt * c) {

	a->left = c;
	c->parent = a; 

	b->right = c->left;
	if (c->left) (c->left)->parent = b;

	c->left = b;
	b->parent = c;
	a->left = c->right;
	if (c->right) (c->right)->parent = a;
	
	if (!a->parent) root = c;
	c->parent = a->parent;
	if (a->parent) {
		if ((a->parent)->left == a) (c->parent)->left = c;
		else (c->parent)->right = c;
	}

	c->right = a;
	a->parent = c;

	a->height = max(((a->left) ? (a->left)->height : 0 ) , ((a->right) ? (a->right)->height : 0 ))+1;
	b->height = max(((b->left) ? (b->left)->height : 0 ) , ((b->right) ? (b->right)->height : 0 ))+1;
	c->height = max(((c->left) ? (c->left)->height : 0 ) , ((c->right) ? (c->right)->height : 0 ))+1;

	a->pod = 0;
	if (a->right) a->pod += (a->right)->pod+1;
	if (a->left) a->pod += (a->left)->pod+1;
	
	b->pod = 0;
	if (b->right) b->pod += (b->right)->pod+1;
	if (b->left) b->pod += (b->left)->pod+1;

	c->pod = 0;
	if (c->right) c->pod += (c->right)->pod+1;
	if (c->left) c->pod += (c->left)->pod+1;
}

inline int max (int a, int b) {
	return ((a>b) ? a : b);
}

void validiate(pkt * x) {
	if (x!=0) {
		validiate(x->left);
		
		if (x->left && x->klucz != ((x->left)->parent)->klucz) {
			printf("Err: Lewe dziecko %d %d\n", x->left->klucz, (x->left)->parent->klucz);
			return;
		}
		if (x->right && x->klucz != ((x->right)->parent)->klucz){
			printf("Err: Prawe dziecko\n");
			return;
		}
		if (x->parent) {
			if ((x->parent)->left == x) {
				if (((x->parent)->left)->klucz != x->klucz) {
					printf("Err: Parent nie pokazuje na dziecko\n");
					return;
				}
			} else if ((x->parent)->right == x) {
				if (((x->parent)->right)->klucz != x->klucz) {
					printf("Err: Parent nie pokazuje na dziecko\n");
					return;
				}
			} else {
				printf("Err: Parent nie pokazuje na dziecko\n");
				return;
			}
		}

		if ( abs( ((x->left) ? (x->left)->height : 0) - ((x->right) ? (x->right)->height : 0) ) > 1 || x->height != max(((x->left) ? (x->left)->height : 0 ) , ((x->right) ? (x->right)->height : 0 ))+1) {
			printf("Err: waga\n");
			return;
		}
		if (x->pod != ((x->left) ? (x->left)->pod+1 : 0)+((x->right) ? (x->right)->pod+1 : 0)) {
			printf("Err: wzbogacanie\n");
			return;
		}

		validiate(x->right);		
	}

}

pkt * H (pkt * tmp, int klucz) {
	int order = 0;
	while(tmp) {
		if (order+((tmp->left) ? (tmp->left)->pod+1 : 0)+1 > klucz) {
			tmp = tmp->left;
		} else {
			order+= ((tmp->left) ? (tmp->left)->pod+1 : 0)+1;
			if (order == klucz) break;
			tmp = tmp->right;
		}
	}
	if (tmp)
		return tmp;
	else
		return 0;
}

int G(pkt * tmp, int klucz) {
	int order = 0;
	while(tmp) {
		if (tmp->klucz == klucz) {
			if (tmp->left) {
				order+= (tmp->left)->pod+2;
			} else {
				order+=1;
			}
			break;
		}
		if (tmp->klucz < klucz) {
			if (tmp->left) {
				order+= (tmp->left)->pod+2;
			} else {
				order+=1;
			}
			tmp = tmp->right;
		} else {
			tmp = tmp->left;
		}
	}
	if (tmp)
		return order;
	else
		return 0;
}