310235: CF1802A. Likes

A. Likestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 > 0$, then the $a_i$th person put a like. If $a_i < 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.

Input

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

Output

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.

ExampleInput

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

Output

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 

Note

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

题目大意：
Nikita 最近举办了一轮非常有争议的比赛，之后他的贡献值变化非常快。公告在主页上挂了 n 秒。在第 i 秒，第 |a_i| 个人要么点赞要么取消赞（Nikita 在这个任务中很幸运，没有踩）。如果 a_i > 0，那么第 a_i 个人点了赞。如果 a_i < 0，那么第 -a_i 个人取消了赞。每个人点赞和取消赞的次数不超过一次。一个人如果没有赞过就不能取消赞。由于Nikita在比赛之后的贡献值变得非常糟糕，他想要分析在公告挂在主页上的时候，他的贡献值是如何变化的。他向平台创建者请求给出序列 a_1, a_2, ..., a_n。但是由于平台的不足，序列 a 被打乱了。你需要根据给出的用户活动序列，告诉每个时刻从 1 到 n，帖子可能获得的最大和最小点赞数。

输入数据格式：
输入数据的第一行包含一个数字 t (1 ≤ t ≤ 1000) —— 测试用例的数量。
每个测试用例的第一行包含一个数字 n (1 ≤ n ≤ 100) —— Nikita的公告挂在主页上的秒数。
下一行包含 n 个数字 b_1, b_2, b_3, ..., b_n (1 ≤ |b_i| ≤ n) —— 混乱的数组 a。保证存在这样的 b 的排列，它是描述条件的正确的事件序列。
保证所有输入测试用例的 n 之和不超过 10^4。

输出数据格式：
对于每个测试用例，输出两行，每行包含 n 个数字。
第一行，对于每个测试用例，输出在第 i 秒Nikita可能获得的最大点赞数。
第二行，对于每个测试用例，输出在第 i 秒Nikita可能获得的最小点赞数。

示例：
输入：
```
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
```

注意：
在第一个测试用例中，最大值是在排列 1, 2, -2 时达到的。最小值是在排列 2, -2, 1 时达到的。
在第三个测试用例中，所有最大值是在排列 4, 2, 3, 1, -1, -2 时达到的。最小值是在排列 2, -2, 1, -1, 3, 4 时达到的。题目大意： Nikita 最近举办了一轮非常有争议的比赛，之后他的贡献值变化非常快。公告在主页上挂了 n 秒。在第 i 秒，第 |a_i| 个人要么点赞要么取消赞（Nikita 在这个任务中很幸运，没有踩）。如果 a_i > 0，那么第 a_i 个人点了赞。如果 a_i < 0，那么第 -a_i 个人取消了赞。每个人点赞和取消赞的次数不超过一次。一个人如果没有赞过就不能取消赞。由于Nikita在比赛之后的贡献值变得非常糟糕，他想要分析在公告挂在主页上的时候，他的贡献值是如何变化的。他向平台创建者请求给出序列 a_1, a_2, ..., a_n。但是由于平台的不足，序列 a 被打乱了。你需要根据给出的用户活动序列，告诉每个时刻从 1 到 n，帖子可能获得的最大和最小点赞数。 输入数据格式： 输入数据的第一行包含一个数字 t (1 ≤ t ≤ 1000) —— 测试用例的数量。 每个测试用例的第一行包含一个数字 n (1 ≤ n ≤ 100) —— Nikita的公告挂在主页上的秒数。 下一行包含 n 个数字 b_1, b_2, b_3, ..., b_n (1 ≤ |b_i| ≤ n) —— 混乱的数组 a。保证存在这样的 b 的排列，它是描述条件的正确的事件序列。 保证所有输入测试用例的 n 之和不超过 10^4。 输出数据格式： 对于每个测试用例，输出两行，每行包含 n 个数字。 第一行，对于每个测试用例，输出在第 i 秒Nikita可能获得的最大点赞数。 第二行，对于每个测试用例，输出在第 i 秒Nikita可能获得的最小点赞数。 示例： 输入： ``` 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 ``` 注意： 在第一个测试用例中，最大值是在排列 1, 2, -2 时达到的。最小值是在排列 2, -2, 1 时达到的。 在第三个测试用例中，所有最大值是在排列 4, 2, 3, 1, -1, -2 时达到的。最小值是在排列 2, -2, 1, -1, 3, 4 时达到的。