#include<bits/stdc++.h>
using namespace std;
typedef struct{
  int key;
  int left,right,parent;
}node;

node t[500005];

int find(int key,int u){
  if(t[u].key==key)
    return 1;
  if(u==-1)
    return 0;
  
  int rec=0;
  if(key>t[u].key)
    rec+=find(key,t[u].right);
  if(key<t[u].key)
    rec+=find(key,t[u].left);
	      
  return rec;
}

void pre(int u){
  printf(" %d",t[u].key);

  if(t[u].left!=-1)pre(t[u].left);
  if(t[u].right!=-1)pre(t[u].right);
  
  return;
}

void in(int u){
  
  if(t[u].left!=-1)in(t[u].left);
  printf(" %d",t[u].key);
  if(t[u].right!=-1)in(t[u].right);

  return;
}

int main()
{

  for(int i=0;i<500005;i++){
    t[i]=(node){-2000000001,-1,-1,-1};
  }

  int n;
  string q;
  int a;
  int next=0;

  cin >> n;
  for(int i=0;i<n;i++){
    cin >> q;
    if(q=="insert"){
      cin >> a;
      int b=0;
      int num=0;
      if(next==0){
	t[next].key=a;
      }else{
	while(num!=-1){
	  b=num;
	  if(t[num].key<a){
	    num=t[num].right;
	  }else{
	    num=t[num].left;
	  }
	}
	if(t[b].key<a){
	  t[b].right=next;
	}else{
	  t[b].left=next;
	}
	t[next].key=a;
	t[next].parent=b;
      }
      next++;
    }

    if(q=="print"){
      in(0);
      printf("\n");
      pre(0);
      printf("\n");
    }

    if(q=="find"){
      cin >> a;
      if(find(a,0))
	cout << "yes" << endl;
      else
	cout << "no" << endl;
    }
  }

  return (0);
}
### Prompt

Please provide a cpp coded solution 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;
typedef struct{
  int key;
  int left,right,parent;
}node;

node t[500005];

int find(int key,int u){
  if(t[u].key==key)
    return 1;
  if(u==-1)
    return 0;
  
  int rec=0;
  if(key>t[u].key)
    rec+=find(key,t[u].right);
  if(key<t[u].key)
    rec+=find(key,t[u].left);
	      
  return rec;
}

void pre(int u){
  printf(" %d",t[u].key);

  if(t[u].left!=-1)pre(t[u].left);
  if(t[u].right!=-1)pre(t[u].right);
  
  return;
}

void in(int u){
  
  if(t[u].left!=-1)in(t[u].left);
  printf(" %d",t[u].key);
  if(t[u].right!=-1)in(t[u].right);

  return;
}

int main()
{

  for(int i=0;i<500005;i++){
    t[i]=(node){-2000000001,-1,-1,-1};
  }

  int n;
  string q;
  int a;
  int next=0;

  cin >> n;
  for(int i=0;i<n;i++){
    cin >> q;
    if(q=="insert"){
      cin >> a;
      int b=0;
      int num=0;
      if(next==0){
	t[next].key=a;
      }else{
	while(num!=-1){
	  b=num;
	  if(t[num].key<a){
	    num=t[num].right;
	  }else{
	    num=t[num].left;
	  }
	}
	if(t[b].key<a){
	  t[b].right=next;
	}else{
	  t[b].left=next;
	}
	t[next].key=a;
	t[next].parent=b;
      }
      next++;
    }

    if(q=="print"){
      in(0);
      printf("\n");
      pre(0);
      printf("\n");
    }

    if(q=="find"){
      cin >> a;
      if(find(a,0))
	cout << "yes" << endl;
      else
	cout << "no" << endl;
    }
  }

  return (0);
}
```