题目描述

$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。

3 3
1 1 1
0
1
2

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}$。