Nikita 最近进行了一场非常有争议的回合,此后他的贡献变化很快。
该公告在主页上挂了 $$$n$$$ 秒。在第 $$$i$$$ 第二个 $$$|a_i|$$$ 中,第 $$$|a_i|$$$ 个人要么点赞,要么删除点赞(尼基塔在这项任务中很幸运,没有不喜欢的人)。如果 $$$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$$$) — Nikita 的公告在主页上挂起的秒数。
下一行包含 $$$n$$$ 数字 $$$b_1, b_2, b_3, \ldots, b_n$$$ ($$$1 \leqslant |b_i| \leqslant n$$$) — 混合数组 $$$a$$$。保证存在这样的 $$$b$$$ 排列,它是条件中描述的事件的正确序列。
保证所有输入测试用例的$$$n$$$总和不超过$$$10^4$$$。
输出
对于每个测试用例,输出两行,每行包含 $$$n$$$ 数字。
在第一行中,对于每个测试用例,输出 Nikita 在第 $$$i$$$ 秒的公告中可能获得的最大点赞数。
在第二行中,对于每个测试用例,输出 Nikita 在第 $$$i$$$ 秒的公告中可能获得的最小点赞数。
示例
输入 #1
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
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
注意
在第一个测试用例中,通过以下排列达到最大值:$$$1, 2, -2$$$。其最小值为:$$$2、-2、1$$$。
在第三个测试用例中,通过以下排列达到所有最大值:$$$4, 2, 3, 1, -1, -2$$$。下一个排列的最小值:$$$2, -2, 1, -1, 3, 4$$$。