#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
struct Node{
	int key;
	Node *parent, *left, *right;
	Node():parent(NULL),left(NULL),right(NULL),key(0){ }
};
Node *root=NULL;int m,cnt=0;
Node * insert(int k,Node *r){
	if(!r){
		r=new Node;
		r->key=k;
	}else if(k>r->key) {
		r->right=insert(k,r->right);
	}else {
		r->left=insert(k,r->left);
	}
	return r;
}
void inorder(Node * r){
	if(!r)return;
	inorder(r->left);
	cout<<" "<<r->key;
	inorder(r->right);
}
void preorder(Node *r){
	if(!r)return ;
	cout<<" "<<r->key;
	preorder(r->left);
	preorder(r->right);
}
void print(){
	cnt=0;
	inorder(root);
	putchar('\n');
	cnt=0;
	preorder(root);
	putchar('\n');
}
bool find(int k,Node * r){
	if(!r) return false;
	if(k==r->key)return true;
	bool flag=false;
	if(k>r->key) flag|=find(k,r->right);
	else flag|=find(k,r->left);
	return flag;
}
int main(){
	int key;
	string s;
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>s;
		if(s=="insert"){
			cin>>key;
			root=insert(key,root);
		}else if(s=="print"){
			print();
		}else if(s=="find"){
			cin>>key;
			cout<< (find(key,root)?"yes":"no") <<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<cstdio>
#include<string>
using namespace std;
struct Node{
	int key;
	Node *parent, *left, *right;
	Node():parent(NULL),left(NULL),right(NULL),key(0){ }
};
Node *root=NULL;int m,cnt=0;
Node * insert(int k,Node *r){
	if(!r){
		r=new Node;
		r->key=k;
	}else if(k>r->key) {
		r->right=insert(k,r->right);
	}else {
		r->left=insert(k,r->left);
	}
	return r;
}
void inorder(Node * r){
	if(!r)return;
	inorder(r->left);
	cout<<" "<<r->key;
	inorder(r->right);
}
void preorder(Node *r){
	if(!r)return ;
	cout<<" "<<r->key;
	preorder(r->left);
	preorder(r->right);
}
void print(){
	cnt=0;
	inorder(root);
	putchar('\n');
	cnt=0;
	preorder(root);
	putchar('\n');
}
bool find(int k,Node * r){
	if(!r) return false;
	if(k==r->key)return true;
	bool flag=false;
	if(k>r->key) flag|=find(k,r->right);
	else flag|=find(k,r->left);
	return flag;
}
int main(){
	int key;
	string s;
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>s;
		if(s=="insert"){
			cin>>key;
			root=insert(key,root);
		}else if(s=="print"){
			print();
		}else if(s=="find"){
			cin>>key;
			cout<< (find(key,root)?"yes":"no") <<endl; 
		}
	}
	return 0;
}

```