给一个只含有大写字母A,B,C,D,E,F,G,H的字符串，对它进行01编码，使得编码后的字符串长度最小。求编码方式和编码后的结果。

Input

一行，一个如题目描述的字符串，长度<=10000。

Output

前八行为这些字母的编码，第九行为编码后的01串。

Sample Input1

ABCDEFGH

Sample Output1

A 000
B 001
C 010
D 011
E 100
F 101
G 110
H 111
000001010011100101110111

Sample Input2

AAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBCDEFGH

Sample Output2

A 0
B 10
C 11111
D 11110
E 11101
F 11100
G 1101
H 1100
000000000000000000000000010101010101010101111111110111011110011011100