Description

给定两个整数 $a$ 和 $b$。你需要将区间 $[a, b]$ 中的所有数字按照某种顺序拼接，形成一个尽可能大的数字 $x$。

接下来有 $q$ 次查询，每次查询给出一个整数 $k$，询问数字 $x$ 的第 $k$ 位是什么。注意，$x$ 的位数从 0 开始编号，最高位为第 0 位。

题目保证对于所有查询，$x$ 的长度至少为 $k + 1$。

Input Format

第一行包含两个整数 $a$ 和 $b$ ($0 < a \leq b \leq 10^{17}$)。

第二行包含一个整数 $q$ ($1 \leq q \leq 5 \cdot 10^4$)，表示查询次数。

第三行包含 $q$ 个整数 $k_1, k_2, \dots, k_q$ ($0 \leq k_i \leq 2 \cdot 10^{18}$)，表示每次查询的位置。题目保证所有查询的答案都存在。

Output Format

输出一行，包含一个长度为 $q$ 的字符串，其中第 $i$ 个字符表示第 $i$ 次查询的答案。

8 13
4
0 3 8 9

9310

Hint

• （$4$ 分）：$b - a \leq 7$；
• （$4$ 分）：$a$ 和 $b$ 的位数相同；
• （$10$ 分）：$b - a \leq 100000$；
• （$33$ 分）：$q \leq 30$；
• （$23$ 分）：$q \leq 1\,000$；
• （$16$ 分）：$q \leq 10\,000$；
• （$10$ 分）：无额外限制。

翻译由 DeepSeek V3 完成