P5956 [POI 2017] Divisibility

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$).

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 $q$ lines, each containing one integer, answering the queries in order. If that position does not exist, output $-1$.

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