Background

$$\begin{aligned}\text{sdjvlajdiofjoiw{\color{1f1e33}n}eglaj}\\\text{pcji{\color{1f1e33}2}gweiruitowoeuri}\\\text{cnvak{\color{1f1e33}5}jflkjweirqoiru}\\\text{rrrwei{\color{1f1e33}f}dlskfjqfafdfaff}\\\text{nmslfjwiejfijlxkjfq{\color{1f1e33}b}el}\\\text{mmm{\color{1f1e33}b}fsfmkdfmksld}\\\text{erjf{\color{1f1e33}n}kerjkwerjkwjeri}\\\text{sdfafafaf{\color{1f1e33}r}fxvzxvzvzx}\end{aligned}$$

Problem Description

Dream has an array of positive integers $a_1, a_2, \dots, a_n$ of length $n$ ($1 \le n \le 10^5$). For $i = 1, 2, \dots, n$, it satisfies $1 \le a_i \le 1000$.

He computed the prefix sum array $p_i = a_1 + a_2 + \dots + a_i$, and it is guaranteed that in the original prefix sum array, for any $1 \le i < n$, we have $p_i < p_{i+1}$.

Now Tommy stole this array and replaced some elements of $p$ with $-1$. Given the current array $p$, restore any valid $a_1, a_2, \dots, a_n$. It can be proven that there is always at least one array $a_i$ that satisfies the requirements.

Input Format

This problem contains multiple test cases. The first line contains a positive integer $t$, the number of test cases. Then follow $t$ test cases. For each test case:

The first line contains an integer $n$.

The second line contains $n$ integers $p_i$, representing the prefix sum sequence.

Output Format

For each test case:

Output one line with $n$ integers, representing one array $a_i$ that satisfies the requirements.

2
5
10 -1 20 -1 30
6
-1 -1 -1 -1 -1 -1

10 5 5 5 5
1 1 4 5 1 4

Hint

Explanation for Sample 1

The output sequence $a_i$ must satisfy the conditions:

• $p_1 = 10 = a_1$;
• $p_3 = 20 = a_1 + a_2 + a_3$;
• $p_5 = 30 = a_1 + a_2 + a_3 + a_4 + a_5$.

Constraints

For $100\%$ of the testdata, $1 \le n, \sum n \le 10^5$, and it is guaranteed that there exists at least one valid array $a$.

• Subtask 1 (50 pts): For $i = 1, 2, \dots, n$, $p_i \neq -1$;
• Subtask 2 (30 pts): It is guaranteed that there does not exist an $i$ such that $p_i = p_{i+1} = -1$;
• Subtask 3 (20 pts): No special restrictions.

Translated by ChatGPT 5