타타라몬

제시와 제임스는 마을 곳곳에 사는 작은 생물인 타타라몬을 잡으러 나선다. 타타라몬을 잡으려면 먼저 싸운 다음 타타라볼에 넣어야 한다.

로켓에 실린 컴퓨터가 두 사람이 지나갈 길에서 만나게 될 타타라몬을 순서대로 예측했다. 타타라몬은 종류마다 고유한 번호가 있다. 예를 들어 25번 타타라몬의 이름은 판단카츄다.

두 사람은 욕심을 부리지 않기로 하고 같은 종류의 타타라몬을 최대 두 마리까지만 잡는다. 그러면서도 하루가 끝났을 때 잡은 타타라몬의 번호를 모두 더한 값은 가능한 한 크게 만들려고 한다.

만나는 순서대로 주어진 타타라몬의 번호 목록에서 같은 번호를 두 번까지만 고르면서 고른 번호의 합을 최대로 만들어야 한다. 잡은 타타라몬은 만난 순서를 그대로 유지하므로 답은 원래 수열의 부분 수열이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 정수 $N$이 주어진다. 둘째 줄에는 제시와 제임스가 만나는 순서대로 타타라몬의 번호 $A_1, A_2, \dots, A_N$이 공백 하나로 구분되어 주어진다.

• $1 \le T \le 10$
• $1 \le N \le 100000$
• $1 \le A_i \le 10^9$

각 테스트 케이스마다 잡아야 하는 타타라몬의 번호 $B_1, B_2, \dots, B_M$을 공백으로 구분해 한 줄에 출력한다. 번호는 입력에서 만난 순서를 그대로 따라야 하므로 $B_1, \dots, B_M$은 $A_1, \dots, A_N$의 부분 수열이다.

번호의 합이 최대인 부분 수열은 여러 개일 수 있다. 이때는 사전 순으로 가장 앞서는 것 하나만 출력한다. 합이 최대인 부분 수열은 길이가 모두 같으므로, 두 부분 수열을 앞에서부터 비교해 처음으로 값이 달라지는 자리에서 더 작은 값을 가진 쪽이 사전 순으로 앞선다.