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

class node{
	public:
		node* left;
		node* right;
		node* p;
		int key;
		node(){
			left=NULL;
			right=NULL;
			p=NULL;
		}
		node(int k){
			left=NULL;
			right=NULL;
			p=NULL;
			key=k;
		}
};

node* root=NULL;
int a[500002];
int n=0;

void insert(node*);
void print();
void preorder(node*);
void midorder(node*);

void insert(node* z){
	node *y=NULL;
	node *x=root;
	while(x!=NULL){
		y=x;
		if(z->key<x->key)x=x->left;
		else x=x->right;
	}
	z->p=y;
	if(y==NULL){
		// delete root;
		root=z;
	// cout<<"root:"<<root->key<<endl;
	}else if(z->key<y->key)y->left=z;
	else y->right=z;
}

void print(){
	midorder(root);
	cout<<endl;
	preorder(root);
	cout<<endl;
}

string find(int k){
	node* x=root;
	while(x!=NULL){
		if(x->key==k)return "yes";
		if(k<x->key)x=x->left;
		else x=x->right;
	}
	return "no";
}

void midorder(node* i){
	if(i==NULL)return;
	midorder(i->left);
	// if(i!=root)cout<<" "<<i->key;
	cout<<" "<<i->key;
	midorder(i->right);
}

void preorder(node* i){
	if(i==NULL)return;
	// if(i!=root)cout<<" "<<i->key;
	cout<<" "<<i->key;
	preorder(i->left);
	preorder(i->right);
}

int main(void){
	int q,k;
	string s;
	cin>>q;
	while(q--){
		cin>>s;
		if(s[0]=='i'){
			cin>>k;
			insert(new node(k));
		}else if(s[0]=='p'){
			print();
		}else if(s[0]=='f'){
			cin>>k;
			cout<<find(k)<<endl;
		}
	}
	return 0;
}
### Prompt

Your challenge is to write a Cpp solution to the following problem:

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 <iostream>
#include <vector>
#include <string>
using namespace std;

class node{
	public:
		node* left;
		node* right;
		node* p;
		int key;
		node(){
			left=NULL;
			right=NULL;
			p=NULL;
		}
		node(int k){
			left=NULL;
			right=NULL;
			p=NULL;
			key=k;
		}
};

node* root=NULL;
int a[500002];
int n=0;

void insert(node*);
void print();
void preorder(node*);
void midorder(node*);

void insert(node* z){
	node *y=NULL;
	node *x=root;
	while(x!=NULL){
		y=x;
		if(z->key<x->key)x=x->left;
		else x=x->right;
	}
	z->p=y;
	if(y==NULL){
		// delete root;
		root=z;
	// cout<<"root:"<<root->key<<endl;
	}else if(z->key<y->key)y->left=z;
	else y->right=z;
}

void print(){
	midorder(root);
	cout<<endl;
	preorder(root);
	cout<<endl;
}

string find(int k){
	node* x=root;
	while(x!=NULL){
		if(x->key==k)return "yes";
		if(k<x->key)x=x->left;
		else x=x->right;
	}
	return "no";
}

void midorder(node* i){
	if(i==NULL)return;
	midorder(i->left);
	// if(i!=root)cout<<" "<<i->key;
	cout<<" "<<i->key;
	midorder(i->right);
}

void preorder(node* i){
	if(i==NULL)return;
	// if(i!=root)cout<<" "<<i->key;
	cout<<" "<<i->key;
	preorder(i->left);
	preorder(i->right);
}

int main(void){
	int q,k;
	string s;
	cin>>q;
	while(q--){
		cin>>s;
		if(s[0]=='i'){
			cin>>k;
			insert(new node(k));
		}else if(s[0]=='p'){
			print();
		}else if(s[0]=='f'){
			cin>>k;
			cout<<find(k)<<endl;
		}
	}
	return 0;
}
```