题目背景

题目描述

Dream 有一个长度为 $n$（$1\le n\le 10^5$）的正整数数组 $a_1,a_2,\dots,a_n$，其中对于 $i=1,2,\dots,n$，满足 $1\le a_i\le 1000$。

他计算了前缀和数组 $p_i=a_1+a_2+\dots+a_i$，保证对于 原前缀和数组 有任意 $1 \le i <n$ 都有 $p_i<p_{i+1}$。

现在 Tommy 偷走了这个数组以及将 $p$ 的若干个元素替代为 $-1$。给定当前的 $p$ 数组，请恢复任意一组合法 $a_1,a_2,\dots,a_n$，可证明一定存在一个数组 $a_i$ 满足要求。

输入格式

本题有多组数据，第一行一个正整数 $t$，为数据组数。接下来 $t$ 组数据，其中对于每一组数据：

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_i$ 代表前缀和序列。

输出格式

对于每一组数据：

一行 $n$ 个整数代表一组满足要求的 $a_i$。

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

提示

样例 1 解释

输出的序列 $a_i$ 一定满足要求：

• $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$。

数据规模与约定

对于 $100\%$ 的数据，$1\le n,\sum n\le 10^5$，并保证存在至少一个合法 $a$ 数组。

• Subtask 1（50 pts）：对于 $i=1,2,\dots,n$，$p_i\neq -1$；
• Subtask 2（30 pts）：保证不存在 $i$ 使得 $p_i=p_{i+1}=-1$；
• Subtask 3（20 pts）：无特殊限制。