Problem J
Fireworks

The Acme Fireworks Company conducts its shows using a custom-designed firing line with multiple launchers. When multiple shells are fired simultaneously, Acme uses launchers that are spread out as far as possible. For example, when two shells are fired simultaneously, Acme uses the leftmost and rightmost launchers. When three shells are fired, it uses the leftmost launcher, the rightmost launcher, and the launcher that is closest to the center.

Things get complicated as the number of simultaneously fired shells increases. Acme’s goal is always to make the smallest of the separations between adjacent launchers as large as possible. For example, below is one of Acme’s firing lines. The launchers are labeled $L_0$ through $L_6$, and the distance in meters between each pair of launchers is given.

When three shells are fired, launchers $L_0$, $L_3$ and $L_6$ are used. Stations $L_0$ and $L_3$ are separated by nine meters while stations $L_3$ and $L_6$ are separated by eight. The smallest separation is eight meters, and since there’s no approach that yields a smallest separation that is higher than eight, the solution is optimal.

Now suppose five shells are fired. The optimal smallest separation of four meters is obtained by using launchers $L_0$, $L_2$, $L_3$, $L_4$ and $L_6$.

Input

The first line contains the number $n$ of launchers and the number $k$ of scenarios to consider, where $2 \le n \le 1000000$ and $1 \le k \le 100$. The next $n-1$ lines contain the distances between launchers, with line $i$ containing the separation between $L_{i-1}$ and $L_ i$. The sum of the separations is never larger than $10^9$. Each of the remaining $k$ lines describes a scenario by giving the number of shells to fire, where $2 \le s \le n$ for each scenario $s$.

Output

For each scenario, print the optimal smallest separation, followed by a newline.

4 1
1
2
3
3

3

7 3
1
3
5
4
2
2
3
5
6

8
4
2

12 1
1
1
1
1
1
500000000
1
1
1
1
1
12

1