#include<iostream>
#include<algorithm>
using namespace std;

typedef struct node Node;
typedef long long ll;

struct node{
  ll val;
  Node *lft,*rht;
};

Node* Insert(Node*,ll);
bool Find(Node*,ll);
void PrintInOrder(Node*);
void PrintPreOrder(Node*);

int main(int argc,char* argv[]){
  Node *root=NULL;
  int n;
  ll x;
  string str;

  cin>>n;
  for(int i=0;i<n;i++){
    cin>>str;
    switch(str[0]){
    case 'i':
      cin>>x;
      root = Insert(root,x);
      break;
    case 'f':
      cin>>x;
      if(Find(root,x))
	cout<<"yes"<<endl;
      else
	cout<<"no"<<endl;
      break;
    case 'p':
      PrintInOrder(root); cout<<endl;
      PrintPreOrder(root); cout<<endl;
      break;
    }
  }

  return 0;
}

Node* Insert(Node *p,ll x){
  if(p == NULL){
    Node *q = new Node;
    q->val = x;
    q->lft = q->rht = NULL;
    return q;
  }
  else if(x < p->val)
    p->lft = Insert(p->lft,x);
  else
    p->rht = Insert(p->rht,x);

  return p;
}

bool Find(Node *p,ll x){
  if(p == NULL)
    return false;
  else if(x == p->val)
    return true;
  else if(x < p->val)
    return Find(p->lft,x);
  else
    return Find(p->rht,x);
}

void PrintInOrder(Node *p){
  if(p != NULL){
    PrintInOrder(p->lft);

    cout<<" "<<p->val;

    PrintInOrder(p->rht);
  }
}

void PrintPreOrder(Node *p){
  if(p != NULL){
    cout<<" "<<p->val;

    PrintPreOrder(p->lft);
    PrintPreOrder(p->rht);
  }
}
### Prompt

Create a solution in Cpp for 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<algorithm>
using namespace std;

typedef struct node Node;
typedef long long ll;

struct node{
  ll val;
  Node *lft,*rht;
};

Node* Insert(Node*,ll);
bool Find(Node*,ll);
void PrintInOrder(Node*);
void PrintPreOrder(Node*);

int main(int argc,char* argv[]){
  Node *root=NULL;
  int n;
  ll x;
  string str;

  cin>>n;
  for(int i=0;i<n;i++){
    cin>>str;
    switch(str[0]){
    case 'i':
      cin>>x;
      root = Insert(root,x);
      break;
    case 'f':
      cin>>x;
      if(Find(root,x))
	cout<<"yes"<<endl;
      else
	cout<<"no"<<endl;
      break;
    case 'p':
      PrintInOrder(root); cout<<endl;
      PrintPreOrder(root); cout<<endl;
      break;
    }
  }

  return 0;
}

Node* Insert(Node *p,ll x){
  if(p == NULL){
    Node *q = new Node;
    q->val = x;
    q->lft = q->rht = NULL;
    return q;
  }
  else if(x < p->val)
    p->lft = Insert(p->lft,x);
  else
    p->rht = Insert(p->rht,x);

  return p;
}

bool Find(Node *p,ll x){
  if(p == NULL)
    return false;
  else if(x == p->val)
    return true;
  else if(x < p->val)
    return Find(p->lft,x);
  else
    return Find(p->rht,x);
}

void PrintInOrder(Node *p){
  if(p != NULL){
    PrintInOrder(p->lft);

    cout<<" "<<p->val;

    PrintInOrder(p->rht);
  }
}

void PrintPreOrder(Node *p){
  if(p != NULL){
    cout<<" "<<p->val;

    PrintPreOrder(p->lft);
    PrintPreOrder(p->rht);
  }
}
```