Big#404

Big

3,5 secondes
512 mégaoctets
Very hard

You are given two integers, and . You concatenate all the numbers in the range in an order that produces the largest possible number, .

You are given queries of the form: — what is the -th digit of ?

The digits of are -indexed, starting with the most significant one.

It is guaranteed that the length of will be at least k + 1.

Input

The first line contains two integers and (0 < a \leq b \leq 10^{17}).

The second line contains one integer (1 \leq q \leq 5 \cdot 10^4).

The third line contains integers k_1, k_2, \dots, k_q (0 \leq k_i \leq 2 \cdot 10^{18}), representing the queries. It is guaranteed that all answers exist.

Output

The only line of the output should contain a string of length , where the -th character will be the answer to the -th query.

Examples

Example 1

Loading
Loading

Scoring

  1. ( points): b - a \leq 7;

  2. ( points): len(a) = len(b);

  3. ( points): b - a \leq 100000

  4. ( points): q \leq 30;

  5. ( points): q \leq 1\,000;

  6. ( points): q \leq 10\,000;

  7. ( points): no further restrictions.