#include<bits/stdc++.h>
using namespace std;
#define NIL 2000000001
typedef struct{
  int p,l,r,key; 
}node;

node tree[500001];
queue<int> q[2];
int root=NIL;

void insert(int key,int i){
  node z={NIL,NIL,NIL,key};
  int x=(root==NIL?NIL:root),y=NIL;
  if(root==NIL)root=i;
  while(x!=NIL){
    y=x;
    if(z.key<tree[x].key){
      x=tree[x].l;
    }else{
      x=tree[x].r;
    }
  }
  z.p=y;
  if(y==NIL){
    tree[0]=z;
  }else if(z.key<tree[y].key){
    tree[y].l=i;
  }else {
    tree[y].r=i;
  }
  tree[i]=z;
}

void print(int n=0){
  if(n==NIL)return;
  q[1].push(tree[n].key);
  print(tree[n].l);
  q[0].push(tree[n].key);
  print(tree[n].r);
}

int find(int key){
  int f=0,x=root;
  while(x!=NIL){
    if(tree[x].key>key){
      x=tree[x].l;
    }else if(tree[x].key<key){
      x=tree[x].r;
    }else{
      f=1;
      break;
    }
  }
  return f;
}

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    string a;
    cin>>a;
    
    if(a[0]=='i'){   
      int k;
      cin>>k;
      insert(k,i);
      
    }else if(a[0]=='f'){
      int key;
      cin>>key;
      cout<<(find(key)?"yes":"no")<<endl;
    }else{
      print();
      for(int j=0;j<2;j++){
	while(!q[j].empty()){
	  cout<<" "<<q[j].front();
	  q[j].pop();
	}
	cout<<endl;
      }
    }
  }
  return 0;
}
### Prompt

Generate 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<bits/stdc++.h>
using namespace std;
#define NIL 2000000001
typedef struct{
  int p,l,r,key; 
}node;

node tree[500001];
queue<int> q[2];
int root=NIL;

void insert(int key,int i){
  node z={NIL,NIL,NIL,key};
  int x=(root==NIL?NIL:root),y=NIL;
  if(root==NIL)root=i;
  while(x!=NIL){
    y=x;
    if(z.key<tree[x].key){
      x=tree[x].l;
    }else{
      x=tree[x].r;
    }
  }
  z.p=y;
  if(y==NIL){
    tree[0]=z;
  }else if(z.key<tree[y].key){
    tree[y].l=i;
  }else {
    tree[y].r=i;
  }
  tree[i]=z;
}

void print(int n=0){
  if(n==NIL)return;
  q[1].push(tree[n].key);
  print(tree[n].l);
  q[0].push(tree[n].key);
  print(tree[n].r);
}

int find(int key){
  int f=0,x=root;
  while(x!=NIL){
    if(tree[x].key>key){
      x=tree[x].l;
    }else if(tree[x].key<key){
      x=tree[x].r;
    }else{
      f=1;
      break;
    }
  }
  return f;
}

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    string a;
    cin>>a;
    
    if(a[0]=='i'){   
      int k;
      cin>>k;
      insert(k,i);
      
    }else if(a[0]=='f'){
      int key;
      cin>>key;
      cout<<(find(key)?"yes":"no")<<endl;
    }else{
      print();
      for(int j=0;j<2;j++){
	while(!q[j].empty()){
	  cout<<" "<<q[j].front();
	  q[j].pop();
	}
	cout<<endl;
      }
    }
  }
  return 0;
}
```