#4724. [POI2017]Podzielno

题目描述

B进制数，每个数字i(i=0,1,...,B-1)有a[i]个。你要用这些数字组成一个最大的B进制数X(不能有前导零，不需要

用完所有数字)，使得X是B-1的倍数。q次询问，每次询问X在B进制下的第k位数字是什么(最低位是第0位)。

输入格式

第一行包含两个正整数B(2<=B<=10^6),q(1<=q<=10^5)。

第二行包含B个正整数a[0],a[1],a[2],...,aB-1。

接下来q行，每行一个整数k(0<=k<=10^18)，表示一个询问。

输出格式

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

样例

样例输入

3 3  

1 1 1  

0  

1  

2

样例输出

0  

2  

-1

数据范围与提示