在上一节信息学课上，Bytie 学习了进位制。特别地，他了解到人们通常使用十进制，而计算机则以二进制存储数字。此外，任何大于 1 的整数 $B$ 都可以作为进位制的基数。在这种系统中，数字为 $0, 1, 2, \dots, B - 2, B - 1$，且 $k$ 位字符串 $c_{k-1}c_{k-2} \dots c_2c_1c_0$ 表示的数值为： $$c_{k-1} \cdot B^{k-1} + c_{k-2} \cdot B^{k-2} + \dots + c_2 \cdot B^2 + c_1 \cdot B + c_0$$

例如，在三进制（即基数为 3）系统中，$201$ 表示数值 $2 \cdot 3^2 + 0 \cdot 3 + 1$，即十进制下的 19，简写为 $201_3 = 19_{10}$。

Bytie 选择了一个特定的数字 $B$ 作为进位制的基数，并在小纸片上写下了该系统的所有 $B$ 个数字，有些数字可能写了多次：对于 $i = 0, 1, \dots, B - 1$，共有 $a_i$ 张写有数字 $i$ 的纸片。Bytie 希望利用这些纸片（数字）组成一个能被 $B - 1$ 整除的最大整数。请编写一个程序来帮助他完成这项任务。他所寻求的数字可能非常大，但只需要输出其中的某些位即可。我们假设正整数的表示形式不能有前导零，且零的唯一合法表示形式是 $0$。

注意：对于基数大于 10 的系统，我们假设数字表示中的各位数字是分开的，例如用空格隔开。这使得以十进制书写的数字能够被唯一解码。

输入格式

标准输入的第一行包含两个整数 $B$ 和 $q$ ($B \ge 2, q \ge 1$)，由单个空格分隔，分别指定了进位制的基数以及 Bytie 对所求数字的位数查询次数。

第二行包含一个由 $B$ 个整数 $a_0, a_1, \dots, a_{B-1}$ ($a_i \ge 1$) 组成的序列，由单个空格分隔，指定了 Bytie 准备的各数字纸片的数量。

接下来的 $q$ 行包含查询：第 $i$ 行包含一个整数 $k_i$ ($0 \le k_i \le 10^{18}$)。

输出格式

标准输出应包含 $q$ 行：第 $i$ 行应包含 Bytie 用他的纸片所能拼出的能被 $B - 1$ 整除的最大整数的第 $k_i$ 位（基数为 $B$）。数字的编号方式如前所述：从右向左（即从最低有效位开始），从第 0 位开始计数。如果所求数字的位数少于 $k_i$，则第 $i$ 行应输出 $-1$。

样例

输入格式 1

3 3
1 1 1
0
1
2

输出格式 1

0
2
-1

说明

对于样例：在三进制系统中，拥有一张 0、一张 1 和一张 2，Bytie 可以组成 $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}$。其中只有 $0_3, 2_3$ 和 $20_3$ 能被 2 整除，因此他所寻求的数字是 $20_3$。

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试组。