CF1802A.Likes

Nikita recently held a very controversial round, after which his contribution changed very quickly.

The announcement hung on the main page for $n$ seconds. In the $i$th second $|a_i|$th person either liked or removed the like (Nikita was lucky in this task and there are no dislikes). If $a_i \gt 0$, then the $a_i$th person put a like. If $a_i \lt 0$, then the person $-a_i$ removed the like. Each person put and removed the like no more than once. A person could not remove a like if he had not put it before.

Since Nikita's contribution became very bad after the round, he wanted to analyze how his contribution changed while the announcement was on the main page. He turned to the creator of the platform with a request to give him the sequence $a_1, a_2, \ldots, a_n$. But due to the imperfection of the platform, the sequence $a$ was shuffled.

You are given a shuffled sequence of $a$ that describes user activity. You need to tell for each moment from $1$ to $n$ what the maximum and minimum number of likes could be on the post at that moment.

尼基塔最近举办了一场极具争议的比赛，赛后他的贡献值发生了剧烈变化。

公告在主页上持续了 $n$ 秒。在第 $i$ 秒，第 $|a_i|$ 个人要么点赞，要么取消点赞（本题中尼基塔运气很好，不存在“点踩”操作）。若 $a_i > 0$，则第 $a_i$ 个人进行了点赞；若 $a_i < 0$，则第 $-a_i$ 个人取消了点赞。每个人至多点赞一次、也至多取消点赞一次；且一个人只有在先前点过赞的前提下，才能取消点赞。

由于该比赛结束后尼基塔的贡献值变得非常糟糕，他希望分析公告在主页展示期间其贡献值的变化情况。他向平台开发者请求提供原始序列 $a_1, a_2, \ldots, a_n$。但由于平台存在缺陷，所获得的序列 $a$ 已被随机打乱。

你将得到一个被打乱后的序列 $a$，它描述了用户的全部操作行为。你需要对从第 $1$ 秒到第 $n$ 秒的每一时刻，分别给出此时帖子上可能达到的最多和最少点赞数。

The first line of input data contains one number $t$ ($1 \leqslant t \leqslant 1000$) — the number of test cases.

In the first line of test case, one number is given $n$ ($1 \leqslant n \leqslant 100$) — the number of seconds during which Nikita's announcement hung on the main page.

The next line contains $n$ numbers $b_1, b_2, b_3, \ldots, b_n$ ($1 \leqslant |b_i| \leqslant n$) — mixed array $a$. It is guaranteed that there exists such a permutation of $b$ that it is a correct sequence of events described in the condition.

It is guaranteed that the sum of $n$ for all input test cases does not exceed $10^4$.

输入数据的第一行包含一个整数 $t$（$1 \leqslant t \leqslant 1000$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leqslant n \leqslant 100$）—— 尼基塔的公告在主页上显示的秒数。

接下来的一行包含 $n$ 个整数 $b_1, b_2, b_3, \ldots, b_n$（$1 \leqslant |b_i| \leqslant n$）—— 混合数组 $a$。题目保证存在 $b$ 的某种排列，使其成为题面描述中所要求的合法事件序列。

保证所有测试用例的 $n$ 值之和不超过 $10^4$。

For each test case, output two lines, each of which contains $n$ numbers.

In the first line, for each test case, output the maximum number of likes that Nikita could have at the announcement at the $i$th second.

In the second line, for each test case, output the minimum number of likes that Nikita could have at the announcement at the $i$th second.

对于每个测试用例，输出两行，每行包含 $n$ 个数字。

第一行：对于每个测试用例，输出 Nikita 在第 $i$ 秒的公告上可能获得的最大点赞数。

第二行：对于每个测试用例，输出 Nikita 在第 $i$ 秒的公告上可能获得的最小点赞数。

In the first test case, the maximum values are reached with the following permutation: $1, 2, -2$. And the minimum values for such: $2, -2, 1$.

In the third test case, all maximal values are reached with the following permutation: $4, 2, 3, 1, -1, -2$. And the minimum values for the next permutation: $2, -2, 1, -1, 3, 4$.

在第一个测试用例中，最大值通过以下排列达到：$1, 2, -2$；而最小值则通过如下排列达到：$2, -2, 1$。

在第三个测试用例中，所有最大值均通过以下排列达到：$4, 2, 3, 1, -1, -2$；而最小值则通过下一个排列达到：$2, -2, 1, -1, 3, 4$。