As de Spade

„Asul de spade reprezintă judecata — o tăiere în punctul ideal. Cu rațiunea și logica trebuie să tai între bine și rău.” Așa trebuie să alegi și pe ce probleme să-ți pierzi timpul.

Se dau două numere naturale $A$ și $B$ unde $A ≤ B$. Toate numerele naturale din intervalul $[A, B]$ se vor concatena într-o ordine oarecare astfel încât să formeze un număr (foarte mare) $G$ cât mai mare. De exemplu, pentru intervalul $[1, 3]$, valoarea lui $G$ este $321$.

Cerință

Se cere să se răspundă la $Q$ întrebări de forma: „Care este cifra de pe poziția $K$ din numărul $G$, considerând că prima cifră a numărului $G$ se află pe poziția $0$?”. Se garantează că acea poziție există.

Date de intrare

Pe prima linie a intrării se află două numere $A$ și $B$.

Pe cea de a doua linie se află un singur întreg reprezentând numărul de întrebări $Q$.

Pe cea de a treia linie se află $Q$ întregi, reprezentând valorile $K$ din cele $Q$ întrebări.

Date de ieșire

Ieșirea trebuie să conțină un șir continuu format din $Q$ cifre, al $i$-lea caracter din șir reprezentând răspunsul la cea de $i$-a întrebare. Nu se vor afișa spații între cifre.

Restricții și precizări

• $1 \leq A \leq B \leq 10^{17}$
• $1 \leq Q \leq 50 \ 000$
• Atenție! Fie $x, y, z$ trei numere naturale. Notăm cu $xy, xz, yz$ etc. concatenarea numerelor $x, y, x, z, y, z$. Se poate demonstra că, dacă $xy ≤ yx$ și $yz ≤ zy$, atunci $xz ≤ zx$.

Exemplul 1

stdin

8 13
4
0 3 8 9

stdout

9310

Explicație

$G = 9813121110$

Exemplul 2

stdin

1 144
15
0 1 2 3 4 5 6 7 8
9 10 11 12 13 14

stdout

999989796959493