题目描述

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

1
5
10 -1 20 -1 30

10 5 5 5 5

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

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