[POI2017]Podzielno

题目描述

$B$ 进制数,每个数字 $i \in [0,B)$ 有 $a_i$ 个。你要用这些数字组成一个最大的 $B$ 进制数 $X$(不能有前导零,不需要用完所有数字),使得 $X$ 是 $B-1$ 的倍数。 $q$ 次询问,每次询问 $X$ 在 $B$进制下的第 $k$ 位数字是什么(最低位是第 $0$ 位)。

输入输出格式

输入格式


第一行包含两个正整数 $B,q$。 第二行包含 $B$ 个正整数 $a_0,a_1,a_2,...,a_{B-1}$。 接下来 $q$ 行,每行一个整数 $k$,表示一个询问。

输出格式


输出 $q$ 行,每行一个整数,依次回答每个询问,如果那一位不存在,请输出 `-1`。

输入输出样例

输入样例 #1

3 3
1 1 1
0
1
2

输出样例 #1

0
2 
-1

说明

对于 $100\%$ 的数据,$2\le B\le10^6$,$1\le q\le 10^5$,$1\le a_i\le10^6$,$0\le k\le10^{18}$。