The Bases Are Loaded

Input

Each line of input contains three values. The first is the base of the given number, the second is the target base, and the third is the number itself. The number may contain digits (including uppercase Latin letters for digits above $9$) that are invalid for the provided base. The number will contain at most $10$ characters. Each line's values are separated by at least one space.

Output

For each case, output the original number, a space, the word $\text{base}$, a space, the original base, a space, $\text{=}$, a space, the converted number, a space, $\text{base}$, and a space, the target base. If the number is not valid in the original base, output:

\text{original\_number}\ \textbf{is an illegal base}\ \text{original\_base}\ \textbf{number}

Examples