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

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

Input

The first line contains the number n of launchers and the number k of scenarios to consider, where 1≤≤10000001≤n≤1000000 and 1≤≤1001≤k≤100. The next −1n−1 lines contain the distances between launchers, with line i containing the separation between −1Li−1 and Li. The sum of the separations is never larger than 109109. Each of the remaining k lines describes a scenario by giving the number of shells to fire, where 2≤≤2≤s≤n for each scenario s.