#include <stdio.h>
#include <stdlib.h>

typedef struct my_tree {
	struct my_tree *left;
	struct my_tree *right;
	struct my_tree *parent;
	int key;
} tree;


tree* add(tree *root, int key) {
	tree *node = root, *node_prev = NULL;

	while (node) {
		node_prev = node;
		if (node->key == key) {
			return root;
		}

		node = (node->key > key) ? node->left : node->right;
	}

	tree *new_node = malloc(sizeof(tree));
	new_node->parent = node_prev;
	new_node->left = NULL;
	new_node->right = NULL;
	new_node->key = key;

	if (!node_prev) {
		root = new_node;
	} else if (node_prev->key > key) {
		node_prev->left = new_node;
	} else if (node_prev->key < key) {
		node_prev->right = new_node;
	}

	return root;
}


void print(tree *root) {
	if (root == NULL)
		return;

	print(root->left);
	print(root->right);

	printf("%d ", root->key);
}




int main(void) {
	int val;
	tree *tr = NULL;

	scanf("%d", &val);

	while(val >= 0) {
		tr = add(tr, val);
		print(tr);
		printf("\n");
		scanf("%d", &val);

	}

	print(tr);

	return 0;
}