Bound Found

Time limit1sMemory limit128 MB

Summary

For multiple targets, find the contiguous subarray whose absolute sum is closest to the target, reporting that absolute sum.

Level: Medium6 of 10
Topics: Prefix sum, Sorting, Binary search, Two pointers
Solved: No attempts yet

Problem

Signals believed to be of extra-terrestrial origin have been received and converted into integer data. Each signal comes in two parts: a sequence of $n$ integers and a non-negative integer target $t$ .

You are given a sequence of $n$ integers $a_1, a_2, \ldots, a_n$ and a non-negative target $t$ . For every non-empty contiguous subrange $a_l, a_{l+1}, \ldots, a_u$ ( $1 \le l \le u \le n$ ), define its absolute sum as $|a_l + a_{l+1} + \cdots + a_u|$ .

Among all subranges, find the one whose absolute sum is closest to $t$ — that is, the one minimizing $|(\text{absolute sum}) - t|$ — and output that absolute sum. If two distinct absolute sums are equally close to $t$ , output the smaller one.

Input

The input consists of several test cases. Each test case starts with two integers $n$ and $k$ . The input is terminated by a case with $n = k = 0$ . Otherwise $1 \le n \le 100000$ , followed by the $n$ integers that make up the sequence, each with absolute value at most $10000$ . Then follow $k$ queries for this sequence; each query is a single target $t$ with $0 \le t \le 1000000000$ .

Output

For each query, output on its own line the absolute sum of the subrange whose absolute sum is closest to $t$ : the value $|a_l + \cdots + a_u|$ for a non-empty subrange that minimizes $|(\text{absolute sum}) - t|$ . If two absolute sums are equally close, output the smaller one.

Examples3

Example 1

Input

5 1
-10 -5 0 5 10
3
10 2
-9 8 -7 6 -5 4 -3 2 -1 0
5 11
15 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
15 100
0 0

Expected output

Example 2
Input
```
1 1
7
3
0 0
```
Expected output
```
7
```
Example 3
Input
```
2 1
4 2
5
0 0
```
Expected output
```
4
```