가장 가까운 절댓값 합

우주에서 온 것으로 추정되는 신호가 수신되어 정수 데이터로 변환되었습니다. 각 신호는 두 부분으로 이루어집니다. 정수 $n$개로 이루어진 수열과, 음이 아닌 정수 목표값 $t$입니다.

길이 $n$인 정수 수열 $a_1, a_2, \ldots, a_n$과 음이 아닌 목표값 $t$가 주어집니다. 비어 있지 않은 연속 부분 구간 $a_l, a_{l+1}, \ldots, a_u$ ($1 \le l \le u \le n$) 각각에 대해, 그 절댓값 합을 $|a_l + a_{l+1} + \cdots + a_u|$로 정의합니다.

모든 부분 구간 중에서 절댓값 합이 $t$에 가장 가까운, 즉 $|(\text{절댓값 합}) - t|$를 최소로 만드는 구간을 찾아 그 절댓값 합을 출력하세요. 만약 서로 다른 두 절댓값 합이 $t$로부터 똑같이 가깝다면 더 작은 값을 출력합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 두 정수 $n$과 $k$로 시작합니다. $n = k = 0$인 경우 입력이 종료됩니다. 그 외의 경우 $1 \le n \le 100000$이며, 이어서 수열을 이루는 정수 $n$개가 주어집니다. 각 정수의 절댓값은 $10000$ 이하입니다. 그다음 이 수열에 대한 질의 $k$개가 주어지며, 각 질의는 목표값 $t$ 하나로 $0 \le t \le 1000000000$입니다.

각 질의마다, 절댓값 합이 $t$에 가장 가까운 부분 구간의 절댓값 합을 한 줄에 하나씩 출력합니다. 즉 $|(\text{절댓값 합}) - t|$를 최소로 만드는, 비어 있지 않은 구간의 $|a_l + \cdots + a_u|$ 값을 출력하며, 똑같이 가까운 절댓값 합이 두 개 있으면 더 작은 값을 출력합니다.