import java.util.Scanner;
public class BT {
	public BT leftChild; 
	public BT rightChild;
	String key;
	String value; 
	boolean isLeaf; 

	// per Konvention ist ein Blatt einfach null 
	public BT (String key, String value, BT leftChild, BT rightChild) {
		this.key = key ;
		this.value = value;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
		this.isLeaf = false; 
	}
	public BT () {
		this.isLeaf = true; 
		key = null;
		value = null;
		leftChild = null;
		rightChild = null;
	}

	public String find (String key) {
		if (this.isLeaf) 
			return null; 
		if (key.compareTo (this.key) == 0) {
			return this.value;
		}
		else if (key.compareTo (this.key) < 0) {
			return this.leftChild.find(key);
		}
		else  {
			return rightChild.find(key);
		}		
	}

	public void insert (String key, String value) {
		if (this.isLeaf) {
			this.isLeaf = false; 
			this.key = key;
			this.value = value; 
			this.leftChild = new BT();
			this.rightChild = new BT(); 
		}
		else if (key.compareTo (this.key)==0) {
			this.value = value; 
		}
		else if (key.compareTo (this.key) < 0) {
			leftChild.insert(key,value);
		}
		else {
			rightChild.insert(key,value);
		}
	}

	public void delete (String x) {
		if (this.isLeaf) {
			return;
		}
		else if (key.compareTo (this.key) < 0) {
			this.leftChild.delete(key);
		}
		else if (key.compareTo (this.key) > 0) {
			this.rightChild.delete(key);
		}
		else {
			deleteRoot();
		}
	}

	public void deleteRoot() {

	 // key und this.key sind gleich 
		if (this.leftChild.isLeaf) {
			// ersetze alle Daten durch die des rechten Teilbaumes
			BT T1 = rightChild.leftChild;
			BT T2 = rightChild.rightChild;
			value = rightChild.value;
			key = rightChild.key; 
			isLeaf = rightChild.isLeaf; 
			leftChild = T1; 
			rightChild = T2; 
		} 
		else if (this.rightChild.isLeaf) {
			// ersetze alle Daten durch die des rechten Teilbaumes
			BT t1 = leftChild.leftChild;
			BT t2 = leftChild.rightChild;
			value = leftChild.value;
			key = leftChild.key; 
			isLeaf = leftChild.isLeaf; 
			leftChild = t1; 
			rightChild = t2; 
		}
		else {
			/* Baum hat die Struktur 
			((T1, u, T2), x, T3)

			also (T1, y, T2) ist linker Teilbaum, T3 ist rechter Teilbaum 

			Wir bauen jetzt den Baum um:

			(T1, u, (T2, x, T3)), eine Rechtsrotation

			und loeschen dann die Wurzel im rechten Teilbaum 

			*/

			BT t1 = leftChild.leftChild;
			BT t2 = leftChild.rightChild;
			BT t3 = rightChild; 
			String newKey = leftChild.key ;
			String newValue = leftChild.value; 

			BT newRight = new BT(key, value, t2, t3);
			newRight.deleteRoot(); 

			key = newKey;
			value = newKey;

			leftChild = t1; 
			rightChild = newRight; 
		}
	}

	public String toString (String prefix) {
		if (isLeaf) {
			return "";
		}
		String result = prefix + key + ": " + value + "\n";
		result += leftChild.toString (prefix + "  |" );
		result += rightChild.toString (prefix + "  |");
		return result;
	}
	public String toString () {
		return toString ("");
	}




	public static void main (String args[]) {
		BT tree = new BT();
	
	
		Scanner scanner = new Scanner (System.in); 
		while (scanner.hasNext()) {
			String command = scanner.next();
			if (command.equals("find")) {
				String key = scanner.next(); 
				String value = tree.find(key);
				System.out.println("\t" + value);
			}
			else if (command.equals("delete")) {
				String key = scanner.next(); 
				tree.delete(key);
				// System.out.println("\t" + value);
			}
			else if (command.equals("insert")) {
				String key = scanner.next();
				String value = scanner.next();
				tree.insert(key,value);
				System.out.println("\tinsert okay");
			}

			else if (command.equals("print")) {

				System.out.println(tree.toString());
			}

			else {
				System.out.println("*** unknown command: " + command);
			}
		}
	}

}