Write a program which performs the following operations to a binary search tree $T$ by adding delete operation to B: Binary Search Tree II.

* insert  $k$: Insert a node containing $k$ as key into $T$.
* find $k$: Report whether $T$ has a node containing $k$.
* delete $k$: Delete a node containing $k$.
* print: Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.



The operation delete $k$ for deleting a given node $z$ containing key $k$ from $T$ can be implemented by an algorithm which considers the following cases:

1. If $z$ has no children, we modify its parent $z.p$ to replace $z$ with NIL as its child (delete $z$).
2. If $z$ has only a single child, we "splice out" $z$ by making a new link between its child and its parent.
3. If $z$ has two children, we splice out $z$'s successor $y$ and replace $z$'s key with $y$'s key.

Constraints

* The number of operations $\leq 500,000$
* The number of print operations $\leq 10$.
* $-2,000,000,000 \leq key \leq 2,000,000,000$
* The height of the binary tree does not exceed 100 if you employ the above pseudo code.
* The keys in the binary search tree are all different.

Input

In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$, find $k$, delete $k$ or print are given.

Output

For each find $k$ operation, print "yes" if $T$ has a node containing $k$, "no" if not.

In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key

Example

Input

18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print


Output

yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22
import java.util.Scanner;

class Main {
	static Node node;
	static Node root;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String ins;
		for (int i = 0; i < n; i++) {
			ins = sc.next();
			if (ins.equals("print")) {
				inorder(root);
				System.out.println();
				preorder(root);
				System.out.println();
			} else if (ins.equals("insert")) {
				Node z = new Node();
				z.key = sc.nextInt();
				insert(z);
			} else if (ins.equals("find")) {
				int k = sc.nextInt();
				find(k);
				System.out.println();
			} else if (ins.equals("delete")) {

				Node z = new Node();
				z.key = sc.nextInt();
				delete(z);
			}

		}
	}
	static void inorder(Node node) {
		if (node == null) return;
		inorder(node.l);
		System.out.print(" " + node.key);
		inorder(node.r);
	}

	static void preorder(Node node) {
		if (node == null) return;
		System.out.print(" " + node.key);
		preorder(node.l);
		preorder(node.r);
	}

	static void insert(Node z) {
		if (root == null) {
			root = z;
			return;
		}
		Node y = null;
		Node x = root;
		while (x != null) {
			y = x;
			if (z.key < x.key) x = x.l;
			else x = x.r;
		}

		if (z.key < y.key) y.l = z;
		else y.r = z;
	}

	static void find(int k) {
		node = root;
		while (true) {
			if (node.key > k) {
				if (node.l == null) {
					System.out.print("no");
					return;
				} else {
					node = node.l;
				}
			} else if (node.key < k) {
				if (node.r == null) {
					System.out.print("no");
					return;
				} else {
					node = node.r;
				}
			} else if (node.key == k) {
				System.out.print("yes");
				return;
			}
		}
	}

	static void delete(Node z) {
		Node p = null;
		node = root;
		while (z.key != node.key) {
			p = node;
			if (node.key > z.key) node = node.l;
			else if (node.key < z.key) node = node.r;
		}
		if (node.l == null && node.r == null) {
			if (p.key < node.key) p.r = null;
			else p.l = null;
		} else if (node.l == null) {
			if (p.key < node.key) p.r = node.r;
			else p.l = node.r;
		} else if (node.r == null) {
			if (p.key < node.key) p.r = node.l;
			else p.l = node.l;
		} else {
			Node node2 = node;
			p = node;
			node = node.r;
			while(node.l!=null){
				p = node;
				node = node.l;
			}
			//System.out.println(node.key + " " + node2.key+" "+p.key);
			node2.key = node.key;
			
			if (node.l == null && node.r == null) {
				//System.out.println(node.key + " " + node2.key+" "+p.key);
				if (p.key <= node.key) p.r = null;
				else p.l = null;
			} else if (node.l == null) {
				if (p.key < node.key) p.r = node.r;
				else p.l = node.r;
			} else if (node.r == null) {
				if (p.key < node.key) p.r = node.l;
				else p.l = node.l;
			}
		}
	}
}

class Node {
	int key;
	Node l;
	Node r;
	Node() {
		key = -1;
		l = null;
		r = null;
	}
}