A. Лайки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Никита провел очень противоречивый раунд, после которого его вклад очень быстро менялся.

Анонс висел на главной странице $$$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$$$, какое максимальное и минимальное количество лайков могло быть на посту в этот момент.

Входные данные

В первой строке входных данных дано одно число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите по две строки, в каждой из которых по $$$n$$$ чисел.

В первой строке для каждого набора входных данных выведите максимальное количество лайков, которые Никита мог иметь на анонсе в $$$i$$$-ю секунду.

Во второй строке для каждого набора входных данных выведите минимальное количество лайков, которые Никита мог иметь на анонсе в $$$i$$$-ю секунду.

Пример
Входные данные
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$$$.