스노우볼 timer 2초 memory 1024MB

JOI 평원은 동서 방향으로 퍼지는 매우 큰 평원이다. 이 평원은 직선으로 간주 될 수 있으며 각 지점은 동쪽을 향한 양의 좌표로 표시됩니다. JOI 평원은 겨울을 맞이하여 N 개의 눈덩이가 다른 좌표로 만들어졌습니다. 눈덩이에는 서쪽부터 순서대로 1에서 N까지의 번호가 붙어 있다. 첫째, 눈덩이 i (1≤i≤N)의 좌표는 정수 X_i이었다. 또한 JOI 평원은 겨울에 강한 바람이 불는 것으로 알려져 있습니다. Q 일간의 바람 관측 데이터를 얻었습니다. j 일째 (1≤j≤Q)의 바람 데이터는 정수 W_j로 표시됩니다. W_j가 음수 일 때 서쪽으로, W_j가 음수가 아닌 경우 동쪽으로 힘 | W_j |의 바람이 불었다는 것을 의미합니다.

바람이 불면 눈덩이는 바람과 같은 방향으로 바람의 강도와 같은 거리만큼 굴러갑니다. 즉, j 일째 (1 ≤ j ≤ Q)의 시작 부분에 좌표 x에 눈덩이가 있었을 때, 그 눈덩이는 좌표 x에서 좌표 x + W_j까지 굴러갑니다. j 날의 끝에서 눈덩이의 좌표는 x + W_j입니다. 그러나 각 날에 모든 눈덩이가 동시에 같은 속도로 굴러갑니다.

처음에는 JOI 평원 전체에 눈이 쌓여 있었다. 눈이 쌓여 있는 범위를 눈덩이가 굴러가면 눈이 부착되어 눈덩이의 무게가 늘어나 그 범위의 눈은 없어진다. 즉, a를 정수로 하고 좌표 a에서 좌표 a + 1까지의 범위에 눈이 남아 있다고 가정합니다. 이 때 눈덩이가이 범위를 굴러 가면 눈덩이의 무게가 1 늘어나고 좌표 a에서 좌표 a + 1까지의 눈이 없어집니다. 그러나 눈이 남지 않는 범위를 눈덩이가 굴러도 눈덩이의 무게는 변하지 않습니다.

처음에는 모든 눈덩이의 무게는 0이었습니다. 또한 관찰 된 Q 일 동안 새롭게 눈이 내리지 않았다.

Q 일의 끝에서 눈덩이의 무게를 알고 싶습니다.

눈덩이의 첫 번째 좌표, Q 일간의 바람의 관측 데이터가 주어지면, Q 일째의 끝에서 각 눈덩이의 무게를 구하는 프로그램을 작성하라.