Problem Description

In base $B$, for each digit $i \in [0,B)$, you have $a_i$ copies. You need to use these digits to form the largest base-$B$ number $X$ (no leading zeros, and you do not need to use all digits), such that $X$ is a multiple of $B-1$. There are $q$ queries. For each query, ask what the digit at position $k$ of $X$ is in base $B$ (the least significant digit is position $0$).

Input Format

The first line contains two positive integers $B, q$.

The second line contains $B$ positive integers $a_0, a_1, a_2, ..., a_{B-1}$.

The next $q$ lines each contain one integer $k$, representing a query.

Output Format

Output $q$ lines, each containing one integer, answering the queries in order. If that position does not exist, output $-1$.

3 3
1 1 1
0
1
2

0
2 
-1

Hint

Constraints: for $100\%$ of the testdata, $2 \le B \le 10^6$, $1 \le q \le 10^5$, $1 \le a_i \le 10^6$, $0 \le k \le 10^{18}$.

Translated by ChatGPT 5