잔디깎이

마르티나스의 집 앞에는 잔디밭이 있습니다. 이 잔디밭은 길이가 $N$ 센티미터인 직선으로 볼 수 있으며, $1$ 센티미터마다 잔디 포기가 하나씩 돋아 있습니다. $i$번째 위치($1 \le i \le N$)의 잔디 포기 높이는 $a_i$ 센티미터입니다.

지금까지 잔디를 한 번도 깎지 않아서 잔디밭을 산책하기도, 소풍을 즐기기도 어려운 상태입니다.

마르티나스는 잔디깎이를 샀고, $M$일에 걸쳐 잔디의 대부분을 깎으려 합니다. $j$번째 날($1 \le j \le M$)에는 다음 일이 순서대로 일어납니다.

• 아침: 아직 완전히 깎이지 않은($a_i \ne 0$) 모든 잔디 포기가 $1\,\text{cm}$ 자랍니다.
• 낮: 마르티나스가 잔디깎이로 잔디밭을 $b_j$번 지나갑니다. 한 번 지나갈 때마다 아직 깎이지 않은 모든 잔디 포기의 높이가 $1\,\text{cm}$씩 줄어듭니다(높이는 $0$ 아래로 내려가지 않습니다).
• 저녁: 아직 남아 있는 잔디의 총 높이(센티미터)를 셉니다.

예를 들어 잔디밭 길이가 $4\,\text{cm}$($N = 4$)이고 잔디 포기의 높이가 각각 $1, 2, 1, 3$이라고 합시다. 마르티나스는 $M = 2$일 동안 일하며, 첫째 날에는 잔디밭을 $b_1 = 2$번, 둘째 날에는 $b_2 = 1$번 지나갑니다.

첫째 날 아침에는 모든 포기가 $1\,\text{cm}$ 자라 $2, 3, 2, 4$가 됩니다. 낮에 잔디밭을 두 번 지나가면 각 포기가 $2\,\text{cm}$씩 줄어 $0, 1, 0, 2$가 되고, 저녁에는 $0 + 1 + 0 + 2 = 3\,\text{cm}$의 잔디가 남습니다.

둘째 날 아침에는 아직 잔디가 남아 있는 포기만 자라(첫째와 셋째 포기는 $0$이므로 그대로) $0, 2, 0, 3$이 됩니다. 낮에 한 번 지나가면 $0, 1, 0, 2$가 되고, 저녁에는 다시 $0 + 1 + 0 + 2 = 3\,\text{cm}$가 남습니다.

잔디밭의 초기 상태와 $M$일 동안의 잔디 깎기 계획이 주어질 때, $M$일 각각의 저녁에 남아 있는 잔디의 총 높이를 구하세요.

• 첫째 줄에 잔디밭의 길이를 나타내는 정수 $N$이 주어집니다.
• 둘째 줄에 공백으로 구분된 $N$개의 정수 $a_i$($1 \le i \le N$) — 잔디 포기들의 높이가 주어집니다.
• 셋째 줄에 마르티나스가 잔디를 깎는 날수를 나타내는 정수 $M$이 주어집니다.
• 넷째 줄에 공백으로 구분된 $M$개의 정수 $b_j$($1 \le j \le M$) — $j$번째 날에 잔디밭을 지나가는 횟수가 주어집니다.

$M$개의 줄을 출력합니다. $k$번째 줄($1 \le k \le M$)에는 $k$번째 날이 끝났을 때 남아 있는 잔디의 총 높이(센티미터)를 나타내는 정수 하나를 출력합니다.

• $1 \le N, M \le 100000$
• $1 \le a_i \le 1000000$ ($1 \le i \le N$)
• $1 \le b_j \le 1000000$ ($1 \le j \le M$)

계산 과정에서 $64$비트 정수 자료형(C/C++의 long long)이 필요할 수 있음에 유의하세요.