#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

struct Node {
	Node *parent, *left, *right;
	int key;
};

Node *root, *nil;

void insert(int& a) {
	Node *b = (Node*)malloc(sizeof(Node)), *c = root, *d = nil;
	b->left = nil;
	b->right = nil;
	b->key = a;
	while (c != nil) {
		d = c;
		if (b->key < c->key) c = c->left;
		else c = c->right;
	}
	b->parent = d;
	if (b->parent == nil) root = b;
	else if (b->key < b->parent->key) b->parent->left = b;
	else b->parent->right = b;
}

bool find(int& a) {
	Node *b = root;
	while (b != nil && a != b->key) {
		if (a < b->key) b = b->left;
		else b = b->right;
	}
	return b != nil;
}

void inorderTreeWalk(Node* a = root) {
	if (a != nil) {
		inorderTreeWalk(a->left);
		cout << ' ' << a->key;
		inorderTreeWalk(a->right);
	}
}

void preorderTreeWalk(Node* a = root) {
	if (a != nil) {
		cout << ' ' << a->key;
		preorderTreeWalk(a->left);
		preorderTreeWalk(a->right);
	}
}

int main() {
	int m, k;
	cin >> m;
	for (int i = 0; i < m; i++) {
		string a;
		cin >> a;
		if (a == "insert") {
			cin >> k;
			insert(k);
		}
		else if (a == "find") {
			cin >> k;
			if (find(k)) cout << "yes";
			else cout << "no";
			cout << endl;
		}
		else {
			inorderTreeWalk();
			cout << endl;
			preorderTreeWalk();
			cout << endl;
		}
	}
}

### Prompt

Develop a solution in cpp to the problem described below:

Write a program which performs the following operations to a binary search tree $T$ by adding the find operation to A: Binary Search Tree I.

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

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$ 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

10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print


Output

yes
no
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

### Response

```cpp
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

struct Node {
	Node *parent, *left, *right;
	int key;
};

Node *root, *nil;

void insert(int& a) {
	Node *b = (Node*)malloc(sizeof(Node)), *c = root, *d = nil;
	b->left = nil;
	b->right = nil;
	b->key = a;
	while (c != nil) {
		d = c;
		if (b->key < c->key) c = c->left;
		else c = c->right;
	}
	b->parent = d;
	if (b->parent == nil) root = b;
	else if (b->key < b->parent->key) b->parent->left = b;
	else b->parent->right = b;
}

bool find(int& a) {
	Node *b = root;
	while (b != nil && a != b->key) {
		if (a < b->key) b = b->left;
		else b = b->right;
	}
	return b != nil;
}

void inorderTreeWalk(Node* a = root) {
	if (a != nil) {
		inorderTreeWalk(a->left);
		cout << ' ' << a->key;
		inorderTreeWalk(a->right);
	}
}

void preorderTreeWalk(Node* a = root) {
	if (a != nil) {
		cout << ' ' << a->key;
		preorderTreeWalk(a->left);
		preorderTreeWalk(a->right);
	}
}

int main() {
	int m, k;
	cin >> m;
	for (int i = 0; i < m; i++) {
		string a;
		cin >> a;
		if (a == "insert") {
			cin >> k;
			insert(k);
		}
		else if (a == "find") {
			cin >> k;
			if (find(k)) cout << "yes";
			else cout << "no";
			cout << endl;
		}
		else {
			inorderTreeWalk();
			cout << endl;
			preorderTreeWalk();
			cout << endl;
		}
	}
}

```