#include<bits/stdc++.h>
using namespace std;
typedef struct node{
	int c;
	struct node *r,*l;  
} *Tree;
void CreateTree(Tree &T,int x){
	if(T==NULL){
	    T=new node;
		T->c=x;
		T->r=NULL;
		T->l=NULL;
		return;
	}
	if(T->c==x) return ;
	else if(x<T->c){
		CreateTree(T->l,x);
	}else{
		CreateTree(T->r,x);
	}
}
void visitPre(Tree T){
	if(T){
		cout<<T->c<<" ";
		visitPre(T->l);
		visitPre(T->r);
	}
}
void visitZ(Tree T){
	if(T){
		visitZ(T->l);
		cout<<T->c<<" ";
		visitZ(T->r);
	}
}
void visitB(Tree T){
	if(T){
		visitB(T->l);
		visitB(T->r);
		cout<<T->c<<" ";
	}
}
int main(){
	int n;
	while(cin>>n){
	Tree T=NULL;
	int x;
	for(int i=0;i<n;i++){
	    cin>>x;
	    CreateTree(T,x);
	    
	}
	visitPre(T);
	cout<<endl;
	visitZ(T);
	cout<<endl;
	visitB(T);
	cout<<endl;
	}
}