Okabe likes writing notes for himself. Since he writes about strange things and does not want others to think he is weird, he encodes all his messages in his own super-secret format. Unfortunately for Okabe, you — being an amazing cryptanalyst — have figured out his scheme.
First, he maps a character to an integer , and then converts it into another integer
by changing its base. He creates a random list
of
integers, where
is stored in base
, and
is stored in base
. That is,
You've gotten your hands on some of Okabe's notes, and would like to decrypt some values, given
. Can you do it?
Reminder
The notation for representing a number in base
is
.
Input Specification
The first line of input will contain the integers and
.
The next and final line of input will contain space-separated integers making up
, with the
-th integer representing
.
is always given in base
, and it is guaranteed that
can be converted (for every digit
in
,
unless
, when
).
Output Specification
A single integer,
.
Sample Input 1
5 3
10 10 10
Sample Output 1
5
Sample Input 2
5000 4
7 1001 10 2
Sample Output 2
1715
Explanation
Working your way up from ,
Step-by-step,
.
.
.
.
Comments