Crack the Code

Over the past year you've been taking a hacking course and now it's time to show what you've learned in a test! The test has 1 problem that is simple (or at least that's what your teacher, Mr. Ergastopoulos, says): you have to break a code to get the PIN for a credit card.

Thankfully, you've been taught this way of coding during your course: You can store a number ~x~ within another ~A~ with a parameter: the so-called "base" ~b~. To recover ~x~, knowing ~b, A~ you perform the following calculation:

• c++ / java etc.: x = A % b;
• python: x = A % b

~x~ is thus the remainder of the integer division ~A / b~.

But what happens when you want to store various numbers ~x_1, x_2 \dots x_n~ within ~A~ using ~b~? Mr. Ergastopoulos hasn't taught you how (you do need to do some things by yourself in the exam!), but has told you that you can "clean" ~A~ from ~x_1~ in order to read ~x_2~:

• c++ / java κ.λπ.: x = A / b;
• python: x = A // b

So you divide ~A~ by ~b~ and keep the whole part of the division. Now you can get ~x_2~ , as you learned above.

An example for: ~ b = 10,\quad A = 42~

• To get the first hidden number, you do: ~ x = A\ \%\ b = 42\ \%\ 10 = 2 ~
• To "clear" the first hidden number, you do: ~ A' = A\ /\ b = 42\ /\ 10 = 4.2 \to 4 ~
• To get the second hidden number, you do: ~ x' = A'\ \%\ b = 4\ \%\ 10 = 4 ~
• and so forth.

Problem

Write a script that reads the base ~b~ and the number ~A~ and finds the requested hidden PIN digits.

Examples

1st

STDIN

10 42172413
5
1 2 8 4 2

STDOUT

3
1
4
2
1

Explanation

We break ~A~ into ~x_1, x_2 \dots~:

• ~x_1:\quad 3~
• ~x_2:\quad 1~
• ~x_3:\quad 2~
• ~x_4:\quad 4~
• ~x_5:\quad 7~
• ~x_6:\quad 1~
• ~x_7:\quad 2~
• ~x_8:\quad 4~

The requested digits are therefore: ~ x_1,\ x_2,\ x_8,\ x_4,\ x_2 ~

(we don't care that ~x_2~ is being requested twice, the answer stays the same)

2nd

STDIN

4 343434
3
1 3 5

STDOUT

2
0
1

Restrictions

• ~b \geq 2~
• ~1 \leq A \leq 2 \cdot 10^9~
• ~1 \leq Q \leq 50~
• ~d_i~ always expresses a number that is stored in ~A~ (eg. the third hidden digit in number ~5~ with base ~10~ or the 0th digit of a number will not be requested).

For an extra 20% of the grade, ~1 \leq Q \leq 2 \cdot 10^6, 1 \leq A \leq 2 \cdot 10^{18}~ (use long long instead of int in languages such as C/C++/Java etc.)