Construct Maximum Divisible Number

You are given a base \(B\) and for each digit \(i\) (where \(0 \le i < B\)) a count \(a_i\) indicating how many copies of that digit are available. Using these digits you need to form the largest possible number \(X\) in base \(B\) (you may use a subset of the digits, but the number must not have any leading zeros, unless the number is 0) such that \(X\) is a multiple of \(B-1\). Recall that a number in base \(B\) is divisible by \(B-1\) if and only if the sum of its digits is divisible by \(B-1\), since \(B \equiv 1 \; (\text{mod } B-1)\).

After constructing \(X\), you will be given \(q\) queries. In each query, you are provided a nonnegative integer \(k\) and must output the digit at the \(k\)th position in the base \(B\) representation of \(X\), where the least significant digit (rightmost digit) is at position \(0\). If \(k\) is larger than or equal to the number of digits in \(X\), output \(0\) as the answer for that query.

Input and Output Format: See below.

inputFormat

The first line contains two integers \(B\) and \(q\) \( (2 \le B \le 10,\; 1 \le q \le 10^5)\), representing the base and the number of queries.

B q

The second line contains \(B\) integers \(a_0, a_1, \ldots, a_{B-1}\) (\(0 \le a_i \le 10^9\)).

a_0 a_1 a_2 ... a_{B-1}

Then follow \(q\) lines, each containing a nonnegative integer \(k\), representing the query asking for the \(k\)th digit of \(X\) (with index 0 being the least significant digit).

outputFormat

For each query, output a single digit (in decimal) on its own line — the digit that appears at the specified position in the base \(B\) representation of the maximum number \(X\) that is divisible by \(B-1\). If there is no digit at that position (i.e. the number has fewer than \(k+1\) digits), output 0.

sample

10 3
1 1 1 1 1 1 1 1 1 1
0
1
9

0
1
9