Farmer John alinea sus $N$ vacas ($2\le N\le 10^3$), numeradas $1\ldots N$, para una sesión de fotos. FJ planeaba que la $i$-ésima vaca desde la izquierda tuviera el número $a_i,$ y escribió la permutación $a_1,a_2,\ldots,a_N$ en una hoja. ¡Por desgracia, Farmer Nhoj robó esa hoja recientemente!
Por suerte, FJ quizá aún pueda recuperar la permutación escrita. Antes del robo, Bessie anotó la secuencia $b_1,b_2,\ldots,b_{N-1}$ que cumple $b_i=a_i+a_{i+1}$ para cada $1\le i<N.$
Con la información de Bessie, ayuda a FJ a recuperar la permutación $a$ «lexicográficamente mínima» que pudo producir $b$. Una permutación $x$ es lexicográficamente menor que $y$ si para algún $j$, $x_i=y_i$ para todo $i<j$ y $x_j<y_j$ (son idénticas hasta cierto punto, donde $x$ es menor que $y$). Se garantiza que existe al menos una $a$ así.
Entrada
La primera línea contiene un entero $N.$
La segunda contiene $N-1$ enteros $b_1,b_2,\ldots,b_{N-1}.$ separados por espacios.
Salida
Una línea con $N$ enteros $a_1,a_2,\ldots,a_{N}.$ separados por espacios.
Ejemplos
Entrada 1
5 4 6 7 6
Salida 1
3 1 5 2 4
Nota
$a$ produce $b$ porque $3+1=4$, $1+5=6$, $5+2=7$ y $2+4=6.$
Subtareas
Los casos $2$–$4$ cumplen $N\le 8.$
Los casos $5$–$10$ no tienen restricciones adicionales.
Autores del problema: Benjamin Qi y Chris Zhang