정렬

Alex와 Bob은 형제이며 둘 다 독서를 매우 좋아한다. 두 사람은 책에 대한 취향이 매우 달라서 각자의 책을 따로 보관한다. 하지만 아버지는 책을 한데 모아 두면 서로 교류하는 데 도움이 될 것이라고 생각한다. 그래서 아버지는 오늘 두 사람을 위해 한 줄짜리 책장을 사서 아들들의 책을 모두 무작위 순서로 올려놓았다. 그리고 책장의 각 위치에 해당 책의 소유자('Alex' 또는 'Bob')를 표시했다.

안타깝게도 Alex와 Bob은 외출 중이어서 아버지가 무엇을 했는지 몰랐다. 돌아온 두 사람은 문제를 깨달았다. 평소에는 각자의 순서대로 책을 정리했지만, 지금 책장 위의 책들은 매우 엉망인 것 같았다. 두 사람은 당장 책을 정렬해야 한다!!

각 책에는 고유한 가치가 있으며, 이는 정수로 표현된다. 가치가 홀수인 책은 Alex의 것이고, 가치가 짝수인 책은 Bob의 것이다. Alex는 자신의 책을 왼쪽에서 오른쪽으로 가치의 오름차순으로 정렬하는 습관이 있는 반면, Bob은 자신의 책을 왼쪽에서 오른쪽으로 가치의 내림차순으로 정렬하는 것을 선호한다.

동시에 두 사람은 표시의 위치를 바꾸고 싶어 하지 않는다. 따라서 각자의 규칙에 따라 책 정렬을 마친 뒤에는 각 책 소유자의 이름이 그 책이 놓인 위치의 표시와 일치해야 한다.

이제 문제를 설명한다. 현재 책장에 놓인 책의 가치를 왼쪽에서 오른쪽 순서로 나타내는 N개의 값으로 이루어진 수열 $s_{0}$, $s_{1}$, ..., $s_{N-1}$가 주어진다. 위 설명을 만족하도록 정렬한 뒤의 가치 수열을 형제가 알아낼 수 있게 도와주자.

제한

테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB.

1 ≤ T ≤ 30.

테스트 세트 1 - 공개

1 ≤ N ≤ 100 -100 ≤ $s_{i}$ ≤ 100

테스트 세트 2 - 비공개

1 ≤ N ≤ 1000 -1000 ≤ $s_{i}$ ≤ 1000

입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 T가 주어진다. 각 테스트 케이스는 책장에 놓인 책의 수를 나타내는 정수 N이 포함된 한 줄로 시작한다. 다음 줄에는 책의 가치를 나타내는 N개의 정수 $s_{0}$, $s_{1}$, ..., $s_{N-1}$이 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #X: "에 이어 $t_{0}$, $t_{1}$, ..., $t_{N-1}$을 순서대로 공백으로 구분하여 한 줄에 출력한다. X는 테스트 케이스 번호이며 (1부터 시작한다), $t_{0}$, $t_{1}$, ..., $t_{N-1}$은 책의 가치를 왼쪽에서 오른쪽 순서로 나타내는 결과 수열을 이룬다.