$-1$ 이상의 정수들로 이루어진 길이 $N$의 수열 $A = (A_1, A_2, \dots, A_N)$이 주어집니다. 이 수열과 매개변수 $c$를 사용하여 다음 연산을 수행합니다.

• 처음에 변수 $x := 0$으로 설정합니다.
• $i = 1, 2, \dots, N$에 대하여 다음 연산을 반복합니다.
  • $A_i = -1$이면, $x$를 $x := \max(0, x - c)$로 바꿉니다.
  • 그렇지 않으면, $x$를 $x := x + A_i$로 바꿉니다.

다음과 같은 형태의 $Q$개의 질문에 답하십시오.

• 매개변수 $c = C_i$일 때, 전체 연산 과정에서 $x$가 가질 수 있는 최댓값을 구하십시오.

입력

첫 번째 줄에는 $N$과 $Q$가 이 순서대로 주어집니다. ($1 \le N, Q \le 3 \times 10^5$) 두 번째 줄에는 $N$개의 정수 $A_i$가 주어집니다. ($-1 \le A_i \le 10^6$) 이어지는 $Q$개의 줄에는 각 질문에 대한 $C_i$ 값이 주어집니다. ($0 \le C_i \le 10^6$)

출력

$Q$개의 줄을 출력하십시오. $i$번째 줄에는 $i$번째 질문에 대한 답을 출력하십시오.

예제

입력 1

20 11
50 100 50 100 0 200 -1 50 100 -1 200
-1 200 0 200 -1 200 200 -1 200
30
60
90
180
270
360
540
200
400
600
0

출력 1

1700
1550
1400
950
570
500
500
850
500
500
1850

참고

첫 번째 예제 입력의 첫 번째 질문을 설명합니다.

• 이 질문에서 매개변수는 $c = 30$입니다.
• 처음에 변수는 $x = 0$입니다.
• $A_1 = 50$이므로, $x$는 $x = 0 + 50 = 50$으로 업데이트됩니다.
• $A_2 = 100$이므로, $x$는 $x = 50 + 100 = 150$으로 업데이트됩니다.
• ...
• $A_6 = 200$이므로, $x$는 $x = 300 + 200 = 500$으로 업데이트됩니다.
• $A_7 = -1$이므로, $x$는 $x = \max(0, 500 - 30) = 470$으로 업데이트됩니다.
• ...
• $A_{19} = -1$이므로, $x$는 $x = \max(0, 1530 - 30) = 1500$으로 업데이트됩니다.
• $A_{20} = 200$이므로, $x$는 $x = 1500 + 200 = 1700$으로 업데이트됩니다.

생략된 부분을 포함하여, 전체 연산 과정에서 $x$가 가질 수 있는 최댓값은 $1700$입니다.