#include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
struct node
{
char content;
int value;
bool visit;
node* left;
node* right;
friend bool operator > (const node& a,const node& b)
{
return a.value > b.value;
}
}tree[27],origin[27];
priority_queue <node,vector<node>,greater <node> > q;
string str;
int ch[27],len[27],sign1,sign2;
void huffman()
{
while(q.size()!=1)
{
node n1=q.top();
q.pop();
node n2=q.top();
q.pop();
tree[sign1].content=' ';
tree[sign1].value=n1.value+n2.value;
tree[sign1].left=&n1;
tree[sign1].right=&n2;
tree[sign1].visit=false;
q.push(tree[sign1]);
sign1++;
}
}
void depth_search(node* u,int depth)
{
char c=u->content;
if(c!=' ')
{
if(c=='_')
len[26]=depth;
else if(c>='A'&&c<='Z')
len[c-'A']=depth;
}
u->visit=true;
if(u->left!=NULL&&u->left->visit==false) {depth_search((u->left),depth+1); }
if(u->right!=NULL&&u->right->visit==false) {depth_search((u->right),depth+1);}
}
int main(void)
{
int i;
while(cin>>str&&str!="END")
{
sign1=0; sign2=0;
memset(ch,0,sizeof(ch));
memset(len,0,sizeof(len));
for(i=0;i<str.length();i++)
{
if(str[i]=='_')
ch[26]++;
else
ch[str[i]-'A']++;
}
for(i=0;i<27;i++)
{
if(ch[i]==0) continue;
if(i==26)
origin[sign2].content='_';
else
origin[sign2].content=i+'A';
origin[sign2].value=ch[i];
origin[sign2].visit=false;
origin[sign2].left=NULL; origin[sign2].right=NULL;
q.push(origin[sign2]);
sign2++;
}
node head;//=q.top();
huffman();
head=q.top();
node k=*(head.left);
node m=*(head.right);
node j=*(k.right);
cout<<head.value<<" "<<head.visit<<" "<<head.content<<endl;
cout<<k.value<<" "<<k.visit<<" "<<k.content<<endl;
cout<<m.value<<" "<<m.visit<<" "<<m.content<<endl;
cout<<j.value<<" "<<j.visit<<" "<<j.content<<endl;
depth_search(&head,0);
int sum=0;
for(i=0;i<27;i++)
{
sum+=ch[i]*len[i];
}
cout<<sum<<endl;
}
return 0;
}