책장 정리

Alex와 Bob은 형제이고 둘 다 책 읽기를 좋아한다. 취향이 서로 아주 달라서 각자 자기 책을 따로 보관한다. 아버지는 책을 한곳에 모아 두면 두 아들이 서로 책을 빌려 보리라 생각해서 오늘 한 줄짜리 책장을 사 왔고, 두 아들의 책을 모두 임의의 순서로 꽂았다. 그리고 책장의 각 자리에 그 자리에 놓인 책 주인의 이름('Alex' 또는 'Bob')을 붙였다.

Alex와 Bob은 밖에 나가 있어서 이 사실을 몰랐다. 돌아와서 엉망이 된 책장을 본 두 사람은 지금 당장 책을 정리하기로 했다.

책마다 가치가 정수로 하나씩 정해져 있다. 가치가 홀수인 책은 Alex의 것이고, 짝수인 책은 Bob의 것이다. Alex는 자기 책을 왼쪽에서 오른쪽으로 가치가 커지는 순서로 꽂고, Bob은 자기 책을 왼쪽에서 오른쪽으로 가치가 작아지는 순서로 꽂는다. 가치는 음수일 수도 있으며, 음수의 홀짝은 그 절댓값의 홀짝과 같다.

자리에 붙은 이름표는 옮기지 않는다. 정리를 마친 뒤에도 각 자리에 놓인 책의 주인은 그 자리의 이름표와 같아야 한다.

지금 책장에 왼쪽에서 오른쪽으로 꽂혀 있는 책의 가치 $s_0, s_1, \ldots, s_{N-1}$이 주어진다. 정리를 마친 뒤의 가치 순서를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 책장에 꽂힌 책의 수 $N$이 주어지고, 다음 줄에는 왼쪽부터 순서대로 책의 가치 $s_0, s_1, \ldots, s_{N-1}$이 공백을 사이에 두고 주어진다.

제한

• $1 \le T \le 30$
• $1 \le N \le 1000$
• $-1000 \le s_i \le 1000$

각 테스트 케이스마다 한 줄에 "Case #$X$: "를 출력하고, 이어서 정리를 마친 뒤의 가치 $t_0, t_1, \ldots, t_{N-1}$을 왼쪽부터 순서대로 공백을 사이에 두고 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호다.