Base Conversion

After a long stretch of work, Jeongi finished building a time machine. Curious about the future, Jeongi rode it 500 years forward. Wanting to keep programming there, Jeongi opened an online judge site to solve problems. The future world writes numbers in base $A$, and Jeongi, who is used to base $B$, could not solve anything. Being a strong programmer, Jeongi decided to write a program that converts a number written in base $A$ into base $B$.

Base $N$ means that a single position can hold $N$ different digits. For example, when $N$ is 17, the digits available in one position are 0, 1, 2, ..., 16, which is 17 of them.

The first line contains the base $A$ used in the future world and the base $B$ used by Jeongi, separated by a space. Both $A$ and $B$ are natural numbers between 2 and 30.

The second line contains $m$ ($1 \le m \le 25$), the number of digits in the base $A$ number. The third line contains those $m$ digits, from the highest place down, separated by spaces. Each digit is at least 0 and less than $A$. The number never starts with 0.

The decimal value of the base $A$ number is a positive integer smaller than $2^{20}$.

Print the given number converted to base $B$ on one line. Write each digit as a decimal integer, from the highest place down, and separate consecutive digits with a single space. Do not print a leading 0.