Cheerio Contest 2 P3 - Digits

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Farmer Bob has two numbers A and B, which can be represented as a string of X 9s and a string of Y 9s respectively. He wants to find out the product of A and B (which he will call P). Bob soon realizes that P will be extremely big, so he will ask Q questions about P instead. For the i^\text{th} question, he wants to know the value of the q_i^\text{th} digit in P when counting from the left. Can you write a program to help him?


For all subtasks:

  • 1 \le Q \le 5 \times 10^5
  • q_i will not exceed the number of digits in P.
  • 1 \le X, Y \le 10^{18}
Points Awarded Additional Constraints
2 points 1 \le X, Y \le 9
6 points X = 1 and 1 \le Y \le 10^{18}
7 points No further constraints

Input Specification

The first line contains three integers X, Y and Q.

The next Q lines contain an integer q_i.

Output Specification

Output Q lines, with the i^\text{th} line containing the answer to the i^\text{th} question.

Sample Input

3 4 2

Sample Output


Explanation for Sample

Since A = 999 and B = 9\,999, P = 999 \times 9\,999 = 9\,989\,001.


There are no comments at the moment.