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

typedef struct BiNode{
	char data;
	struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct StackNode
{
	char data;
	struct StackNode *next;
}StackNode,*LinkStack;
char ch;LinkStack S;BiTree T;

void InitStack(LinkStack &S)
{
	S=NULL;
}

void Push(LinkStack &S,char e)
{
	LinkStack p=new StackNode;
	p->data=e;
	p->next=S;
	S=p;
}

int Pop(LinkStack &S,char &e)
{
	if(S==NULL) return 0;
	LinkStack p;
	e=S->data;
	p=S;
	S=S->next;
	delete p;
}

int StackEmpty(LinkStack S)
{
	if(S->next==NULL) return 1;
	return 0;
}
void CreateBiTree(BiTree &T)
{
	cin>>ch;
	if(ch=='#') T=NULL;
	else 
	{
		T=new BiTNode;
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}

void InOrderraverse1(BiTree T)
{
	BiTree p;
	InitStack(S);
	p=T;
	BiTree q=new BiTNode;
	while(p||!StackEmpty(S))
	{
		if(p)
		{
			Push(S,p->data);
			p=p->lchild;
		}
		else 
		{
			Pop(S,q->data);
			cout<<q->data;
			p=q->rchild;
		}
	}
}

void PreOrderTraverse0(BiTree T)
{
	if(T)
	{
		cout<<T->data;
		PreOrderTraverse0(T->lchild);
		PreOrderTraverse0(T->rchild);
	}
}

void InOrderTraverse0(BiTree T)
{
	if(T)
	{
		InOrderTraverse0(T->lchild);
		cout<<T->data;
		InOrderTraverse0(T->rchild);
	}
}

void PosOrderTraverse0(BiTree T)
{
	if(T)
	{
		PosOrderTraverse0(T->lchild);
		PosOrderTraverse0(T->rchild);
		cout<<T->data;
	}
}

int main()
{
	int a; cin>>a;
	CreateBiTree(T);
	if(a==0)
	{
		cout<<"diguibainli"<<endl;
		cout<<"PreOrderTraverse    ";PreOrderTraverse0(T);cout<<endl;
		cout<<"InOrderTraverse     ";InOrderTraverse0(T);cout<<endl;
		cout<<"PosOrderTraverse    ";PosOrderTraverse0(T);cout<<endl;
	}
	else
	{
		InOrderraverse1(T);
	}
	return 0;
}