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.
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.
The only line of the output should contain a string of length , where the -th character will be the answer to the -th query.
Example 1
( points): b - a \leq 7;
( points): len(a) = len(b);
( points): b - a \leq 100000
( points): q \leq 30;
( points): q \leq 1\,000;
( points): q \leq 10\,000;
( points): no further restrictions.