#include<bits/stdc++.h>
using namespace std;

#define bstN 500000
struct bst{
  int size;
  int t[bstN];
  int lc[bstN];
  int rc[bstN];
   
  void init(){
    size=0;
  }
   
  void insert(int v){
    int i=0;
    while(0<=i&&i<size){
      int& child=(v<t[i]?lc[i]:rc[i]);
      if(child==-1)child=size;
      i=child; 
    }
    lc[size]=rc[size]=-1;
    t[size++]=v;
  }

  bool find(int v){
    int i=0;
    while(0<=i&&i<size){
      if(t[i]==v)return true;
      i=(v<t[i]?lc[i]:rc[i]);      
    }
    return false;
  }
  
  void preord(int pos){
    if(pos==-1||pos==size)return;
    preord(lc[pos]);
    printf(" %d",t[pos]);
    preord(rc[pos]);
  }
   
  void inord(int pos){
    if(pos==-1||pos==size)return;
    printf(" %d",t[pos]);
    inord(lc[pos]);
    inord(rc[pos]);
  }
};
 
 
bst T;
 
int main(){
  T.init();
  int n,a;
  char str[100];
  scanf("%d",&n);
   
  while(n--){
    scanf("%s",str);
    if(str[0]=='i'){
      scanf("%d",&a);
      T.insert(a);
    }else if(str[0]=='f'){
      scanf("%d",&a);
      if(T.find(a))printf("yes\n");
      else printf("no\n");      
    }else{
      T.preord(0);
      printf("\n");
      T.inord(0);
      printf("\n");
    }
  }
 
  return 0;
}
### 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<bits/stdc++.h>
using namespace std;

#define bstN 500000
struct bst{
  int size;
  int t[bstN];
  int lc[bstN];
  int rc[bstN];
   
  void init(){
    size=0;
  }
   
  void insert(int v){
    int i=0;
    while(0<=i&&i<size){
      int& child=(v<t[i]?lc[i]:rc[i]);
      if(child==-1)child=size;
      i=child; 
    }
    lc[size]=rc[size]=-1;
    t[size++]=v;
  }

  bool find(int v){
    int i=0;
    while(0<=i&&i<size){
      if(t[i]==v)return true;
      i=(v<t[i]?lc[i]:rc[i]);      
    }
    return false;
  }
  
  void preord(int pos){
    if(pos==-1||pos==size)return;
    preord(lc[pos]);
    printf(" %d",t[pos]);
    preord(rc[pos]);
  }
   
  void inord(int pos){
    if(pos==-1||pos==size)return;
    printf(" %d",t[pos]);
    inord(lc[pos]);
    inord(rc[pos]);
  }
};
 
 
bst T;
 
int main(){
  T.init();
  int n,a;
  char str[100];
  scanf("%d",&n);
   
  while(n--){
    scanf("%s",str);
    if(str[0]=='i'){
      scanf("%d",&a);
      T.insert(a);
    }else if(str[0]=='f'){
      scanf("%d",&a);
      if(T.find(a))printf("yes\n");
      else printf("no\n");      
    }else{
      T.preord(0);
      printf("\n");
      T.inord(0);
      printf("\n");
    }
  }
 
  return 0;
}
```