#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
	char c;
	struct Node *lchild,*rchild;
}*Tree;
Tree create(Tree &T){
	char c;
	cin>>c;
	if(c=='0'){
		T=NULL;
	}
	else
	{
		T = new Node;
		T->c = c;
		T->lchild=NULL;
		T->rchild=NULL;
		create(T->lchild);
		create(T->rchild);
	}
}
void visitPre(Tree T){
	if(T){
	cout<<T->c<<" ";
	visitPre(T->lchild);
	visitPre(T->rchild);
	}
}

void visitBack(Tree T){
	if(T){
	visitBack(T->lchild);
	visitBack(T->rchild);
	cout<<T->c<<" ";
	}
}
void visitZ(Tree T){
	if(T){
	visitZ(T->lchild);
	cout<<T->c<<" ";
	visitZ(T->rchild);
	}
}
int Yz(Tree T){
   if(T==NULL) return 0;
   if(T->lchild == NULL&&T->rchild == NULL) return 1;
   return Yz(T->lchild)+Yz(T->rchild);
}
int main(){
	Tree T = NULL;
	create(T);
	visitPre(T);
	cout<<endl;
	visitZ(T);
	cout<<e...