//////////////////////HEADER
#pragma once
#include <iostream>
#include <string.h>
using namespace std;
class Element
{
	int data;
	char symb;
	Element * straight;
	Element * previous;
	Element * down;
public:
	Element(int a, char b) { symb = b; data = a; straight = 0; down = 0; }
	friend class List;
	friend ostream & operator << (ostream&s, List &a);
};
class List
{
	Element *Ver;
public:
	List() { Ver = 0; }
	void push(char**,int);
	void Dekor(char*,List,char*,int len);
	void Kodir(List a, char * mas, char *,int&);
	friend  ostream & operator << (ostream&s, List &a);
};
char ** SORT(char* str, int &m);


////////////////////////////////////////////////////// MAS
#include "Header.h"

char ** SORT(char* str, int &m)
{
	int i, n = strlen(str);
	char ** mas = new char *[2];
	for (int i = 0; i < 2; i++)
		mas[i] = new char[n];
	for (int i = 0; i < n; i++)
		mas[1][i] = 49;
	for (; *str != 0; str++)
	{
		for (i = 0; i < n && mas[0][i] != *str; i++);
		if (i == n)
		{
			mas[0][m] = *str;
			m++;
		}
		else
			mas[1][i]++;
	}

	int t = 0;
	for (int i = 0; i < m; i++)
	{
		int save, max = 0;
		t = i;
		for (; t < m; t++)
		{
			if (mas[1][t] > max)
			{
				max = mas[1][t];
				save = t;
			}
		}
		max = mas[0][i]; mas[0][i] = mas[0][save]; mas[0][save] = max;
		max = mas[1][i]; mas[1][i] = mas[1][save]; mas[1][save] = max;
	}

	mas[0][m] = '\0';
	mas[1][m] = '\0';
	return mas;
}

///////////////////////////////////////////////////////////SPISOK
#include "Header.h"
void List::push(char** b, int m)
{
	Element *pver;
	Element *pdown;
	int a = b[1][m - 1] - 48;
	for (int i = m - 1; i >= 0; i--)
	{
		if (Ver != 0)
		{
			a += b[1][i] - 48;
			pver = new Element(1, a);
			pdown = new Element(0, b[0][i]);
			Ver->previous = pver;
			pver->straight = Ver;
			pdown->previous = pver;
			pver->down = pdown;
			Ver = pver;
		}
		else
		{
			pver = new Element(1, b[0][i]);
			Ver = pver;
			Ver->straight = 0;
			Ver->down = 0;
		}
	}
}

void List::Kodir(List a, char * mas, char *mas1, int &t)
{
	Element * ptr = a.Ver;
	int data1;
	t = 0;
	for (int i = 0; i < strlen(mas1); i++)
	{
		ptr = a.Ver;
		while (ptr->straight != 0)
		{
			if (ptr->down->symb != mas1[i] && ptr->straight->symb != mas1[i])
				ptr = ptr->straight;
			else
			{
				if (ptr->down->symb == mas1[i])
					data1 = ptr->down->data;
				else
					data1 = ptr->straight->data;

				ptr = ptr->down;
				while (ptr->previous->previous != 0)
				{
					mas[t] = ptr->previous->data + 48;
					t++;
					ptr = ptr->previous;
				}
				mas[t] = data1 + 48;
				t++;
				break;
			}
		}
	}
}

void List::Dekor(char* mas, List a, char*str, int len)
{
	Element*ptr = a.Ver;
	int t = 0;
	for (int i = 0; i < len; i++)
	{
		if (0 == mas[i] - 48)
			ptr = ptr->down;
		else
			ptr = ptr->straight;
		if (ptr->straight == 0)
		{
			str[t] = ptr->symb;
			t++;
			ptr = a.Ver;
		}
	}
	str[t] = '\0';
}

ostream & operator << (ostream&s, List &a)
{
	Element *ptr = a.Ver, *ptrsave = ptr;
	int data;
	char symb;
	while (ptrsave->straight != 0)
	{
		ptr = ptrsave->down;
		data = ptr->data;
		symb = ptr->symb;
		while (ptr->previous->previous != 0)
		{
			ptr = ptr->previous;
			s << ptr->data;
		}
		s << data << " - " << symb << endl;
		ptrsave = ptrsave->straight;
	}
	ptr = ptrsave;
	while (ptr->previous != 0)
	{
		s << ptr->data;
		ptr = ptr->previous;
	}
	s << " - " << ptrsave->symb << endl;
	return s;
}
//////////////////////////////////////////////////////////// main


#include "Header.h"

void main()
{
	const int n = 100000;
	int m = 0;
	char mas[n];
	cin >> mas;
	char ** mas1 = SORT(mas, m);

	cout << endl << endl;
	for (int i = 0; i < m; i++)
		cout << "[" << mas1[0][i] << "]";
	cout << endl;
	for (int i = 0; i < m; i++)
		cout << "[" << mas1[1][i] << "]";
	cout << endl << endl;

	List r;
	r.push(mas1, m);
	cout << r;
	cout << endl << endl;

	int len;
	char mas2[n];
	r.Kodir(r, mas2, mas, len);
	for (int i = 0; i < len; i++)
		cout << mas2[i];
	cout << endl << endl;
	char result[n];
	r.Dekor(mas2, r, result, len);
	cout << result << endl << endl;

	system("pause");
}