Problem G
Sly Students

Image by AVAVA (Shutterstock); Used under license

Students in a boring class want to be able to write notes to each other while removing the threat of the teacher knowing what they are saying if the teacher happens to get hold of a note. Therefore, the students have created a simple way to encode their messages. The encoding involves finding the largest common factor (divisor) of the ASCII values of the characters in each word, something the students call a key, and dividing each ASCII value in the word by this key. The students then represent each resulting quotient in $\textrm{base }3$ (without leading zeros) to form the final encoded message.

For example, the first word of the message “Fix it” contains the ASCII values $70$, $105$, $120$, for ‘F’ ,‘i’, ‘x’, respectively. The largest common factor is $5$, and therefore the values get reduced to $14$, $21$, $24$, and represented in $\textrm{base }3$ as $112$, $210$, $220$. The same procedure is then applied to the word “it” to yield the $\textrm{base-}3$ values $10220$, $11022$.

Create a program that will encode a message, given as a single string, using the students’ encoding method.

Figure 1: The printable characters in the ASCII table (plus SPACE)

Input

The input contains a message in the form of a single string composed of one or more space-separated words, where each word consists of one or more characters with ASCII values in the interval $[33, 126]$. The total number of characters in the message (including spaces) is between $1$ and $10\, 000$, inclusive.

Output

For each word in the message (in order), output two lines, the first of which contains the key for that word, and the second of which contains the encoded word. Separate the encodings of adjacent letters in a word by a single space.

Fix it

5
112 210 220
1
10220 11022

The color of the six inns is blue

1
10010 10212 10202
3
1020 1101 1100 1101 1102
3
1101 1021
1
11022 10212 10202
5
212 210 220
5
210 211 211 212
5
210 212
1
10122 11000 11100 10202