Bola de nieve

Points: 100 (partial)

Time limit: 3.0s

Memory limit: 512M

Authors:

leocar, leo, mdario, albertolg101

Problem type

Allowed languages

C++, Python

Descripción

La llanura OCI es una amplia llanura que se extiende de oeste a este. Podemos considerar la llanura OCI como una recta numérica. Un punto de la llanura OCI se indica mediante una coordenada. La dirección positiva de la recta numérica corresponde a la dirección este. Ahora llega el invierno a la llanura OCI. Hay $N$ ~N~ bolas de nieve en ella, numeradas del $1$ ~1~ al $N$ ~N~ desde el del oeste al este. Al principio, la coordenada de la bola de nieve $i$ ~i~ ( $1 \le i \le N$ ~1 \le i \le N~) es un número entero $X_i$ ~X_i~.

En invierno sopla viento fuerte en la llanura OCI. Se tienen datos de observación del viento durante $Q$ ~Q~ días. En el j-ésimo día ( $1 \le j \le Q$ ~1 \le j \le Q~), el viento se describe mediante un número entero $W_j$ ~W_j~. Si $W_j$ ~W_j~ es negativo, entonces el viento sopla en dirección oeste. Si $W_j$ ~W_j~ no es negativo, entonces el viento sopla en dirección este. La fuerza del viento es | $W_j$ ~W_j~|.

Cuando sopla el viento, una bola de nieve se desplaza en la misma dirección que el viento, y su longitud de desplazamiento es igual a la fuerza del viento. En otras palabras, si hay una bola de nieve en la coordenada $x$ ~x~ al principio del j-ésimo día ( $1 \le j \le Q$ ~1 \le j \le Q~), entonces la bola de nieve se mueve de la coordenada $x$ ~x~ a la coordenada $x$ ~x~ + $W_j$ ~W_j~. Al final del j-ésimo día, la coordenada de la bola de nieve pasa a ser $x$ ~x~ + $W_j$ ~W_j~. Obsérvese que, en cada día, las bolas de nieve se mueven al mismo tiempo, y sus velocidades son las mismas.

Inicialmente, la llanura OCI está cubierta de nieve. Si una bola de nieve se mueve en un intervalo cubierto de nieve, entonces acumula la nieve, el peso de la bola de nieve aumenta y la nieve del intervalo desaparece. En otras palabras, para un número entero $a$ ~a~, supongamos que el intervalo desde $a$ ~a~ hasta $a + 1$ ~a + 1~ está cubierto de nieve. Si se mueve una bola de nieve en este intervalo, entonces el peso de la bola de nieve se incrementa en $1$ ~1~, y la nieve en el intervalo de $a$ ~a~ hasta $a + 1$ ~a + 1~ desaparece. Sin embargo, si se mueve una bola de nieve en un intervalo sin nieve, el peso de la bola de nieve sigue siendo el mismo.

Inicialmente, el peso de cada bola de nieve es $0$ ~0~. No nevó en los días $Q$ ~Q~ de los datos de observación.

Se desea conocer el peso de cada bola de nieve al final del Q-ésimo día.

Tarea

Escribe un programa que, dada la posición inicial de cada bola de nieve y los datos de observación del viento durante $Q$ ~Q~ días calcule el peso de cada bola de nieve al final del día Q-ésimo.

Entrada

Lee los siguientes datos de la entrada estándar. Los valores dados son todos enteros.

$N$ ~N~ $Q$ ~Q~

$X_1$ ~X_1~ - - - $X_N$ ~X_N~

$W_1$ ~W_1~

...

$W_Q$ ~W_Q~

Salida

Escribe N líneas en la salida estándar. La i-ésima línea (1 = i = N) debe contener el peso de la bola de nieve i al al final del día Q-ésimo.

Restricciones

$1 \le N \le 200 000$ ~1 \le N \le 200 000~.
$1 \le Q \le 200 000$ ~1 \le Q \le 200 000~.
| $X_i$ ~X_i~| ≤ $1 000 000 000 000$ ~1 000 000 000 000~ ( $= 10^{12}$ ~= 10^{12}~) ( $1 \le i \le N$ ~1 \le i \le N~).
$X_i$ ~X_i~ < $X_{i+1}$ ~X_{i+1}~ ( $1 \le i \le N - 1$ ~1 \le i \le N - 1~).
| $W_j$ ~W_j~| = $1 000 000 000 000$ ~1 000 000 000 000~ ( $= 10^{12}$ ~= 10^{12}~) ( $1 \le j \le Q$ ~1 \le j \le Q~).

Subtareas

(33 puntos) $N \le 2 000$ ~N \le 2 000~, $Q \le 2 000$ ~Q \le 2 000~.
(67 puntos) No hay restricciones adicionales

Ejemplos de entrada y salida

Ejemplo de Entrada #1

Ejemplo de Salida #1

En esta entrada de ejemplo, el peso de cada bola de nieve varía como sigue.

Inicialmente, las coordenadas de las bolas de nieve son $-2, 3, 5, 8$ ~-2, 3, 5, 8~ de oeste a este. Los pesos de las bolas de nieve son $0, 0, 0, 0,$ ~0, 0, 0, 0,~ respectivamente.
El primer día, el viento sopla en dirección este y su fuerza es $2$ ~2~. Al final del primer día, las coordenadas de las bolas de nieve son coordenadas de las bolas de nieve son $0, 5, 7, 10$ ~0, 5, 7, 10~. Los pesos de las bolas de nieve son $2, 2, 2, 2,$ ~2, 2, 2, 2,~ respectivamente.
El segundo día, el viento sopla en dirección oeste, y su fuerza es $4$ ~4~. Al final del segundo día. Las coordenadas de las bolas de nieve son $-4, 1, 3, 6$ ~-4, 1, 3, 6~. Los pesos de las bolas de nieve son $4, 4, 2, 3,$ ~4, 4, 2, 3,~ respectivamente.
El tercer día, el viento sopla en dirección este, y su fuerza es $7$ ~7~. Al final del tercer día, las coordenadas de las bolas de nieve son $3, 8, 10,$ ~3, 8, 10,~ respectivamente. Las coordenadas de las bolas de nieve son $3, 8, 10, 13$ ~3, 8, 10, 13~. Los pesos de las bolas de nieve son $5, 4, 2, 6,$ ~5, 4, 2, 6,~ respectivamente.

Por lo tanto la salida $5, 4, 2, 6,$ ~5, 4, 2, 6,~ que son los pesos de las bolas de nieve al final del tercer día.

Ejemplo de Entrada #2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

Ejemplo de Salida #2

3000000000000

Ejemplo de Entrada #3

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

Ejemplo de Salida #3

Comments

There are no comments at the moment.