#include<bits/stdc++.h>
using namespace std;
struct node{
	int val;
	char ch;
	node *left, *right;
};
node* create_n(){
	node* ptr= new node;
	ptr->val= 0;
	ptr->ch= '@';
	ptr->left= NULL;
	ptr->right= NULL;
	return ptr;
}
node* create_s(char ch){
	node* r= create_n();
	r->val= 1;
	r->left= create_n();
	r->right= create_n();
	r->right->val= 1;
	r->right->ch= ch;
	return r;
}
void update_count(node* r){
	if (r->left== NULL || r->right== NULL){
		return;
	}
	update_count(r->left);
	update_count(r->right);
	r->val= r->left->val+ r->right->val;
}

vector<vector<node*> > lot(node* r){
	if (r== NULL){
		vector< vector< node*> > v;
		return v;
	}
	vector<vector< node*> > v;
	queue<node*> q;
	q.push(r);
	while(!q.empty()){
		int nodecount= q.size();
		vector<node*> v1;
		while (nodecount--){
			node* ptr= q.front();
			q.pop();
			v1.push_back(ptr);
			if (ptr->left!= NULL){
				q.push(ptr->left);
			}
			if(ptr->right!= NULL){
				q.push(ptr->right);
			}
		}
		v.push_back(v1);
	}
	reverse(v.begin(), v.end());
	return v;
}
bool chk_ascending(node* r){
	vector<vector<node*> > l= lot(r);
	vector<node* > li;
	for(int i=0; i<l.size(); i++){
		for(int j=0; j< l[i].size(); j++){
			li.push_back(l[i][j]);
		}
	}
	for(int i=1; i<li.size(); i++){
		if (li[i-1]->val> li[i]->val){
			return true;
		}
	}
	return false;
}
node* swapping_helper(node* r, node* nts1, node* nts2){
	if (r== NULL){
		return NULL;
	}
	if (r== nts1){
		return nts2;
	}
	if(r== nts2){
		return nts1;
	}
	r->left= swapping_helper(r->left, nts1, nts2);
	r->right= swapping_helper(r->right, nts1, nts2);
	return r;
}
node* swapping(node* r){
	vector<vector<node*> > l= lot(r);
	vector<node* > li;
	for(int i=0; i<l.size(); i++){
		for(int j=0; j< l[i].size(); j++){
			li.push_back(l[i][j]);
		}
	}
	for(int i=1; i<li.size(); i++){
		if (li[i-1]->val> li[i]->val){
			node* nts1= li[i-1];
			node* nts2= NULL;
			int j=i;
			while(j<li.size()){
				if (li[j]->val== li[i-1]->val -1){
					nts2= li[j];
				}
				j++;
			}
			node* ro= swapping_helper(r, nts1, nts2);
			return ro;
		}
	}
	return r;
}
void codewords(node* r, string code){
	if(r== NULL){
		return;
	}
	if(r->ch!='@'){
		cout<<r->ch<<" "<<code<<endl;
		return ;
	}
	codewords(r->left, code+"0");
	codewords(r->right, code+"1");
}

int main(){
	node* root= NULL;
	node* zero_parent= NULL;
	string s;
	cout<<"Enter text: ";
	getline(cin, s);
	unordered_map<char, node*> ar;
	unordered_map<char, int> ar1;
	for(int i=0; i<s.length(); i++){
		if (root== NULL){
			root= create_s(s[i]);
			zero_parent= root;
			ar[s[i]]= zero_parent->right;
			ar1[s[i]]= 1;
			cout<<"After adding "<<s[i]<<"\n";
			codewords(root, "");
			cout<<endl;
			continue;
		}
		if(ar1.find(s[i])!= ar1.end()){
			ar[s[i]]->val+= 1;
			update_count(root);
		}else{
			zero_parent->left= create_s(s[i]);
			zero_parent= zero_parent->left;
			ar1[s[i]]= 1;
			ar[s[i]]= zero_parent->right;

			update_count(root);
		}
		while (chk_ascending(root)){
			root= swapping(root);
			update_count(root);
		}
		cout<<"After adding "<<s[i]<<"\n";
		codewords(root, "");
		cout<<endl;
	}
	cout<<"Codewords: \n";
	codewords(root, "");
	return 0;
}