#include<stdio.h>
#include<iostream>
#include<string>

#define MAX 500000

struct node {
	int key;
	int parent, left, right;
} T[MAX];
int root;

void PrePrint(int t) {
	if (t == -1) return;
	printf(" %d", T[t].key);
	PrePrint(T[t].left);
	PrePrint(T[t].right);
}

void InPrint(int t) {
	if (t == -1) return;
	InPrint(T[t].left);
	printf(" %d", T[t].key);
	InPrint(T[t].right);
}

void initNode(int n) {
	root = -1;
	for (int i = 0; i < n; i++) {
		T[i].key = -1;
		T[i].parent = -1;
		T[i].left = -1;
		T[i].right = -1;
	}
}

void insert(int z) {
	int y = -1; // xの親
	int x = root;
	while (x != -1) {
		y = x;
		if (T[z].key < T[x].key) x = T[x].left;
		else x = T[x].right;
	}
	T[z].parent = y;

	if (y == -1) root = z;
	else if (T[z].key < T[y].key) T[y].left = z;
	else T[y].right = z;
}

bool find(int k) {
	int x = root;
	while (x != -1) {
		if (T[x].key == k) return true;
		if (T[x].key < k) x = T[x].right;
		else x = T[x].left;
	}
	return false;
}

int main() {
	int n = 0;
	scanf("%d", &n);
	initNode(n);
	for (int i = 0; i < n; i++) {
		std::string com;
		std::cin >> com;
		if (com[0] == 'i') {
			int k = 0;
			scanf("%d", &k);
			T[i].key = k;
			insert(i);
		}
		else if (com[0] == 'p') {
			InPrint(root);
			printf("\n");
			PrePrint(root);
			printf("\n");
		}
		else if (com[0] == 'f') {
			int k = 0;
			scanf("%d", &k);
			if (find(k)) {
				printf("yes\n");
			}
			else {
				printf("no\n");
			}
		}
	}
}


### 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<stdio.h>
#include<iostream>
#include<string>

#define MAX 500000

struct node {
	int key;
	int parent, left, right;
} T[MAX];
int root;

void PrePrint(int t) {
	if (t == -1) return;
	printf(" %d", T[t].key);
	PrePrint(T[t].left);
	PrePrint(T[t].right);
}

void InPrint(int t) {
	if (t == -1) return;
	InPrint(T[t].left);
	printf(" %d", T[t].key);
	InPrint(T[t].right);
}

void initNode(int n) {
	root = -1;
	for (int i = 0; i < n; i++) {
		T[i].key = -1;
		T[i].parent = -1;
		T[i].left = -1;
		T[i].right = -1;
	}
}

void insert(int z) {
	int y = -1; // xの親
	int x = root;
	while (x != -1) {
		y = x;
		if (T[z].key < T[x].key) x = T[x].left;
		else x = T[x].right;
	}
	T[z].parent = y;

	if (y == -1) root = z;
	else if (T[z].key < T[y].key) T[y].left = z;
	else T[y].right = z;
}

bool find(int k) {
	int x = root;
	while (x != -1) {
		if (T[x].key == k) return true;
		if (T[x].key < k) x = T[x].right;
		else x = T[x].left;
	}
	return false;
}

int main() {
	int n = 0;
	scanf("%d", &n);
	initNode(n);
	for (int i = 0; i < n; i++) {
		std::string com;
		std::cin >> com;
		if (com[0] == 'i') {
			int k = 0;
			scanf("%d", &k);
			T[i].key = k;
			insert(i);
		}
		else if (com[0] == 'p') {
			InPrint(root);
			printf("\n");
			PrePrint(root);
			printf("\n");
		}
		else if (com[0] == 'f') {
			int k = 0;
			scanf("%d", &k);
			if (find(k)) {
				printf("yes\n");
			}
			else {
				printf("no\n");
			}
		}
	}
}


```