题目描述

Nikita 最近举办了一场非常有争议的比赛，赛后他的贡献度变化得非常快。

公告在主页上悬挂了 $n$ 秒。在第 $i$ 秒，第 $|a_i|$ 号用户要么点赞，要么取消点赞（Nikita 这题很幸运，没有踩）。如果 $a_i > 0$，则第 $a_i$ 号用户点了赞；如果 $a_i < 0$，则 $-a_i$ 号用户取消了点赞。每个用户点赞和取消点赞最多各做一次。如果之前没有点赞，则该用户不能取消点赞。

由于比赛后 Nikita 的贡献度变得非常糟糕，他想分析公告挂在主页期间他的贡献度是如何变化的。他向平台的创建者请求提供 $a_1, a_2, \ldots, a_n$ 的序列。但由于平台不完善，序列 $a$ 被打乱了。

你得到了一个乱序的 $a$ 序列，描述了用户的操作。你需要依次告诉第 $1$ 到第 $n$ 秒时，该帖子上可能的最大和最小点赞数。

输入格式

输入的第一行为一个整数 $t$（$1 \leqslant t \leqslant 1000$），表示测试用例数。

每个测试用例的第一行为一个整数 $n$（$1 \leqslant n \leqslant 100$），表示公告在主页悬挂的秒数。

接下来一行有 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leqslant |b_i| \leqslant n$），表示打乱后的数组 $a$。保证存在某种排列使之为合法操作序列。

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

输出格式

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

第一行为对于每个时刻 $i$，该时刻 Nikita 公告上可能的最大点赞数。

第二行为该时刻可能的最小点赞数。

说明/提示

在第一个测试用例中，最大值由下列排列得到：$1, 2, -2$。而最小值由下列排列得到：$2, -2, 1$。

在第三个测试用例中，所有最大值由排列 $4, 2, 3, 1, -1, -2$ 获得。最小值由如下排列获得：$2, -2, 1, -1, 3, 4$。

由 ChatGPT 5 翻译

样例

5
3
1 2 -2
2
1 -1
6
4 3 -1 2 1 -2
5
4 2 -2 1 3
7
-1 6 -4 3 2 4 1

1 2 1 
1 0 1 
1 0 
1 0 
1 2 3 4 3 2 
1 0 1 0 1 2 
1 2 3 4 3 
1 0 1 2 3 
1 2 3 4 5 4 3 
1 0 1 0 1 2 3