Hide

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 L0 through L6, and the distance in meters between each pair of launchers is given.

\includegraphics[width=0.95\textwidth ]{cropped-diagram.pdf}

When three shells are fired, launchers L0, L3 and L6 are used. Stations L0 and L3 are separated by nine meters while stations L3 and L6 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 L0, L2, L3, L4 and L6.

Input

The first line contains the number n of launchers and the number k of scenarios to consider, where 2n1000000 and 1k100. The next n1 lines contain the distances between launchers, with line i containing the separation between Li1 and Li. The sum of the separations is never larger than 109. Each of the remaining k lines describes a scenario by giving the number of shells to fire, where 2sn for each scenario s.

Output

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

Sample Input 1 Sample Output 1
4 1
1
2
3
3
3
Sample Input 2 Sample Output 2
7 3
1
3
5
4
2
2
3
5
6
8
4
2
Sample Input 3 Sample Output 3
12 1
1
1
1
1
1
500000000
1
1
1
1
1
12
1
Hide

Please log in to submit a solution to this problem

Log in