진법 변환

타임머신을 만들던 정이는 오랜 노력 끝에 타임머신을 완성했다. 미래가 궁금해진 정이는 자신이 만든 타임머신을 타고 500년 뒤의 세계로 떠났다. 500년 뒤에도 프로그래밍을 하고 싶었던 정이는 온라인 저지 사이트에 접속해 문제를 풀기로 했다. 그런데 미래 세계는 $A$진법을 쓰고 있었고, $B$진법에 익숙한 정이는 문제를 풀 수가 없었다. 뛰어난 프로그래머였던 정이는 $A$진법으로 쓴 수를 $B$진법으로 바꿔 주는 프로그램을 만들기로 했다.

$N$진법은 한 자리에 쓸 수 있는 숫자의 가짓수가 $N$이라는 뜻이다. 예를 들어 $N$이 17이면 한 자리에 쓸 수 있는 수는 0, 1, 2, ..., 16으로 모두 17가지다.

첫째 줄에 미래 세계가 쓰는 진법 $A$와 정이가 쓰는 진법 $B$가 공백으로 구분되어 주어진다. $A$와 $B$는 모두 2 이상 30 이하의 자연수다.

둘째 줄에 $A$진법으로 나타낸 수의 자릿수 개수 $m$ ($1 \le m \le 25$)이 주어진다. 셋째 줄에 그 수를 이루는 숫자 $m$개가 높은 자리부터 차례대로 공백으로 구분되어 주어진다. 각 숫자는 0 이상 $A$ 미만이다. 수가 0으로 시작하는 경우는 없다.

$A$진법으로 나타낸 수를 10진법으로 바꾼 값은 양의 정수이며 $2^{20}$보다 작다.

주어진 수를 $B$진법으로 바꿔 한 줄에 출력한다. 높은 자리부터 차례대로 각 자리의 숫자를 10진법 정수로 적고, 숫자 사이를 공백 하나로 구분한다. 맨 앞자리에 0을 붙이지 않는다.