#$4909$. 「POI2017 R1」整除性 Divisibility

题目描述

题目译自 XXIV Olimpiada Informatyczna — I etap Podzielność

最近，Bajtuś 在计算机课上学到了位置计数法。他了解到，人类常用十进制，电脑用二进制，但其实任何大于 $1$ 的自然数 $B$ 都可以作为计数基础。在这样的系统中，可用数字是 $0, 1, 2, \ldots, B-2, B-1$，一个 $k$ 位数 $c_{k-1} c_{k-2} \ldots c_{2} c_{1} c_{0}$ 表示：

$c_{k-1} \cdot B^{k-1} + c_{k-2} \cdot B^{k-2} + \ldots + c_{2} \cdot B^{2} + c_{1} \cdot B + c_{0}$

比如，在三进制中，$201$ 表示 $2 \cdot 3^{2} + 0 \cdot 3 + 1$，也就是十进制的 $19$（简写为 $201_{3} = 19_{10}$）。

Bajtuś 选了个数 $B$ 作为计数基础，把所有可用数字写在卡片上，有些数字可能重复：对于 $i = 0, 1, \ldots, B-1$，他有 $a_{i}$ 张写着 $i$ 的卡片。他想用这些卡片拼出尽可能大的、能被 $B-1$ 整除的数。请你写个程序帮他实现这个目标。这数可能很大，Bajtuś 只想知道某些特定位置的数字即可。注意，正数的写法不能以 $0$ 开头，$0$ 的唯一写法是 $0$。

特别说明：若基础 $B$ 超过 $10$，假设数字间有空格分隔，避免混淆。

输入格式

输入第一行包含两个整数 $B$ 和 $q$ ($B \geq 2, q \geq 1$)，用空格分隔，分别表示计数基础和查询次数。

第二行包含 $B$ 个整数 $a_{0}, a_{1}, \ldots, a_{B-1}$ ($a_{i} \geq 1$)，用空格分隔，表示 Bajtuś 拥有的每个数字 $i$ 的卡片数量。

接下来的 $q$ 行，每行一个整数 $k_{i}$ ($0 \leq k_{i} \leq 10^{18}$)，表示查询目标数的第 $k_{i}$ 位。

输出格式

输出 $q$ 行，第 $i$ 行给出目标数（用 $B$ 进制表示、能被 $B-1$ 整除的最大数）的第 $k_{i}$ 位。位数从右往左数（最低位为 $0$）。若目标数位数少于 $k_{i}$，输出 $-1$。

样例

输入

$3$ $3$ $1$ $1$ $1$ $0$ $1$ $2$

输出

$0$ $2$ $-1$

在三进制中，有一张 $0$、一张 $1$ 和一张 $2$ 的卡片，可拼出：$0_{3} = 0_{10}$、$1_{3} = 1_{10}$、$2_{3} = 2_{10}$、$10_{3} = 3_{10}$、$12_{3} = 5_{10}$、$20_{3} = 6_{10}$、$21_{3} = 7_{10}$、$102_{3} = 11_{10}$、$120_{3} = 15_{10}$、$201_{3} = 19_{10}$、$210_{3} = 21_{10}$。能被 $2$ 整除的有 $0_{3}$、$2_{3}$、$20_{3}$，最大数是 $20_{3}$。

附加样例

$B=10$, $a_{i}=1$, $q=10$, $k_{i}=i-1$； $B=2$, $a_{0}=10000$, $a_{1}=1$, $q=10001$, $k_{i}=i-1$； $B=1000000$, $a_{i}=1$, $q=1$, $k_{1}=999999$。

数据范围与提示

详细子任务附加限制及分值如下表所示。