32637번 - 물통

문제

용량이 $x$인 물통과 정수로 이루어진 수열 $A_1,A_2,\cdots,A_N$이 주어진다. 우리는 물통에 물을 채우거나 빼는 작업을 총 $N$번 수행하고자 한다.

$A_i$가 양수라면 $i$번째 작업은 물통에 물을 $A_i$만큼 채우는 작업이고, 아니라면 물통에 물을 $\left| A_i \right|$만큼 빼는 작업이다.

• 용량보다 많은 물을 채우려고 하면, 물은 물통의 용량까지만 차게 된다.
• 현재 남은 물의 양보다 많은 물을 빼려고 하면, 현재 남아있는 양 만큼만 뺀다.

다음과 같은 쿼리가 총 $M$번 주어진다.

• $y$: 초기에 물을 $y$만큼 채우고 $N$개의 작업을 순서대로 수행하고 나서, 물통에 채워져 있는 물의 양을 출력한다.

입력

첫째 줄에 용량을 나타내는 정수 $x$와 수열의 길이 $N$이 공백을 사이에 두고 주어진다. $(1\leq x\leq 10^{13}, 1\leq N \leq 10^5)$

둘째 줄에 정수로 이루어진 수열 $A_1,A_2,\cdots,A_N$이 주어진다. $(-x \leq A_i \leq x)$

셋째 줄에 쿼리의 개수를 나타내는 정수 $M$이 주어진다. $(1\leq M \leq 10^5)$

넷째 줄부터 $M$개의 줄에 걸쳐 정수 $y$가 주어진다. $(0 \leq y \leq x)$

출력

첫째 줄부터 총 $M$개의 줄에 걸쳐 쿼리가 주어질 때마다 정답을 출력한다.

제한

힌트