#include<iostream>
using namespace std;

struct tr{
	char c;
	tr *l;
	tr *r;
};
int num;

void init(tr* &t)
{
	char c;
	if(cin>>c)
	{
		if(c=='0')
		{
			t=nullptr;
			return;
		}
		else
		{
			t=new tr;
			t->c=c;
			init(t->l),init(t->r);
		}
	}
}
void print1(tr *t)
{
	if(t==nullptr)
		return;
	cout<<t->c<<" ";
	if(t->l==nullptr&&t->r==nullptr)
		num++;
	print1(t->l),print1(t->r);
}
void print2(tr *t)
{
	if(t==nullptr)
		return;
	print2(t->l);
	cout<<t->c<<" ";
	print2(t->r);
}
void print3(tr *t)
{
	if(t==nullptr)
		return;
	print3(t->l);
	print3(t->r);
	cout<<t->c<<" ";
}

int main()
{
	tr *t=nullptr;
	init(t);
	print1(t);
	puts("");
	print2(t);
	puts("");
	print3(t);
	puts("");
	cout<<num;
	return 0;
}