
#include <iostream>  
#include <cstdio>  
#include <cstring> 
#include <cstdlib>
using namespace std;
string s;
int x,m,i;
struct node
{
int data;
struct node * lchild;
struct node * rchild;
};
typedef struct node;
typedef node * tree;
tree root;
void findn(tree bt,int n)
{
    if(bt)
    {
     if(n<bt->data) findn(bt->lchild,n);
     else if(n>bt->data) findn(bt->rchild,n);
  else cout<<"yes"<<endl;
    }
  else cout<<"no"<<endl;
} 
void insert(tree &bt,int n)
{
   if(bt)
    {
       if(n<bt->data)insert(bt->lchild,n);
       else if (n>bt->data)insert(bt->rchild,n);  
    }
    else
    {
        bt=new node;
        bt->data=n;
        bt->lchild=bt->rchild=NULL;
    }  
}

void printh(tree bt)
{
     if(bt)
     {
        cout<<" "<<bt->data;     
        printh(bt->lchild);
        printh(bt->rchild);
         
     }
}
void printz(tree bt)
{
     if(bt)
     {
        printz(bt->lchild);
        cout<<" "<<bt->data;
        printz(bt->rchild);   
     }
}
int main() 
{  
    root=NULL;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
  
     cin>>s;
    
    if(s=="insert")
     {
        cin>>x;
        insert(root,x);            
     }
    if(s=="find")
    {
      cin>>x;
      findn(root,x);           
    }
      if(s=="print")
      {
         printz(root);
         cout<<endl;
         printh(root);
         cout<<endl;            
      }       
    }
    
   //system("pause");  
    return 0;  
}  
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <cstring> 
#include <cstdlib>
using namespace std;
string s;
int x,m,i;
struct node
{
int data;
struct node * lchild;
struct node * rchild;
};
typedef struct node;
typedef node * tree;
tree root;
void findn(tree bt,int n)
{
    if(bt)
    {
     if(n<bt->data) findn(bt->lchild,n);
     else if(n>bt->data) findn(bt->rchild,n);
  else cout<<"yes"<<endl;
    }
  else cout<<"no"<<endl;
} 
void insert(tree &bt,int n)
{
   if(bt)
    {
       if(n<bt->data)insert(bt->lchild,n);
       else if (n>bt->data)insert(bt->rchild,n);  
    }
    else
    {
        bt=new node;
        bt->data=n;
        bt->lchild=bt->rchild=NULL;
    }  
}

void printh(tree bt)
{
     if(bt)
     {
        cout<<" "<<bt->data;     
        printh(bt->lchild);
        printh(bt->rchild);
         
     }
}
void printz(tree bt)
{
     if(bt)
     {
        printz(bt->lchild);
        cout<<" "<<bt->data;
        printz(bt->rchild);   
     }
}
int main() 
{  
    root=NULL;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
  
     cin>>s;
    
    if(s=="insert")
     {
        cin>>x;
        insert(root,x);            
     }
    if(s=="find")
    {
      cin>>x;
      findn(root,x);           
    }
      if(s=="print")
      {
         printz(root);
         cout<<endl;
         printh(root);
         cout<<endl;            
      }       
    }
    
   //system("pause");  
    return 0;  
}  
```