package folder;

import java.util.Scanner;

class BinaryTree {

	static int con = 0;
	static int coun = 0;
	static String back = null;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		BinaryTree tree = new BinaryTree();
		while (in.hasNext()) {
			String acao = in.next();
			if (acao.equals("P")) {
				tree.printPreorder();
				System.out.print('\n');
				con = 0;
			} else if (acao.equals("R")) {
				tree.deletaritem(in.nextInt());
				System.out.println(back);
				back = null;
			} else if (acao.equals("B")) {
				String retorno = tree.buscar(in.nextInt());
				System.out.println(retorno);
			} else if (acao.equals("L")) {
				tree.contagem();
				System.out.println(coun);
				coun = 0;
			} else {
				int nr = Integer.parseInt(acao);
				in.nextLine();
				String a = in.nextLine();
				tree.inserir(nr, a);
			}
		}
	}

	void printPreorder() {
		Preordem(raiz);
	}

	public int contagem() {
		altura(raiz);
		return coun;
	}

	class No {
		int key;
		String extenso;
		No left, right;

		public No(int item, String extenso) {
			key = item;
			this.extenso = extenso;
			left = right = null;
		}
	}

	No raiz;
	String extenso;

	BinaryTree() {
		raiz = null;
		extenso = null;
	}

	void Preordem(No no) {
		if (no != null) {

			if (con > 0) {
				System.out.print("->");
			}
			System.out.print(no.key + ":'" + no.extenso + "'");
			con = 1;
			Preordem(no.left);
			Preordem(no.right);
		}
	}

	void altura(No no) {
		if (no == null) {
			return;
		}
		coun++;
		altura(no.left);
		altura(no.right);

	}

	void inserir(int key, String extenso) {
		raiz = inserirTree(raiz, key, extenso);
	}

	No inserirTree(No raiz, int key, String extenso) {
		if (raiz == null) {
			raiz = new No(key, extenso);
			return raiz;
		}
		if (key < raiz.key) {
			raiz.left = inserirTree(raiz.left, key, extenso);
		} else if (key > raiz.key) {
			raiz.right = inserirTree(raiz.right, key, extenso);
		}
		return raiz;
	}

	public String deletaritem(int key) {

		raiz = deletartree(raiz, key);
		return raiz.extenso;

	}

	No deletartree(No root, int key) {

		if (root == null) {
			return raiz;
		} else if (key < root.key) {
			root.left = deletartree(root.left, key);

		} else if (key > root.key) {
			root.right = deletartree(root.right, key);

		} else {
			if (root.left == null) {
				back = root.extenso;
				return root.right;
			} else if (root.right == null) {
				back = root.extenso;
				return root.left;
			}
			root.key = minValue(root.right);
			root.right = deletartree(root.right, root.key);
		}

		return raiz;
	}

	int minValue(No raiz) {
		int minv = raiz.key;
		while (raiz.left != null) {
			minv = raiz.left.key;
			raiz = raiz.left;
		}
		return minv;
	}

	public String buscar(int key) {
		String resul = busca(raiz, key);
		return resul;
	}

	public String busca(No root, int key) {
		if (root == null || root.key == key) {
			return root.extenso;
		} else if (root.key > key) {
			return busca(root.left, key);
		} else {
			return busca(root.right, key);
		}
	}
}