/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 */

#include <bits/stdc++.h>
#include "optimization.h"

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

struct node {
	int cnt, l, r;
};
vector<node> v;
struct cmp {
	bool operator() ( int i, int j ) const { return v[i].cnt > v[j].cnt; }
};

int main() {
	char s[100000 + 1];
	int len;
	readWord(s);

	v.assign(26, node {0, -1, -1});
	for (len = 0; s[len]; len++)
		v[s[len] - 'a'].cnt++;
	priority_queue<int, vector<int>, cmp> q;
	forn(i, 26)
	 if (v[i].cnt > 0)
		 q.push(i);
	
	int ans = (q.size() == 1U ? len : 0);
	printf("%d ", (int)q.size());
	while (q.size() > 1U) {
		int l = q.top(); q.pop();
		int r = q.top(); q.pop();
		ans += v[l].cnt + v[r].cnt;
		v.push_back(node {v[l].cnt + v[r].cnt, l, r});
		q.push(v.size() - 1);
	}

	printf("%d\n", ans);
	vector<string> code(26);
	function<void(int,string)> go = [&]( int i, string str ) {
		if (v[i].l == -1) {
			printf("%c: %s\n", 'a' + i, (code[i] = (str == "" ? "0" : str)).c_str());
			return;
		}
		go(v[i].l, str + "0");
		go(v[i].r, str + "1");
	};
	go(q.top(), "");
	fflush(stdout);
	for (int i = 0; s[i]; i++)
		writeWord(code[s[i] - 'a'].c_str());
}
