학생과 멘토

$\mathbf{N}$명의 학생으로 이루어진 한 그룹이 Google의 Kick Start와 Code Jam 같은 다가오는 프로그래밍 대회를 함께 준비한다. 서로의 준비를 돕기 위해, 각 학생은 다른 학생들 중에서 멘토를 한 명 선택하기로 했다. 멘토는 멘티가 문제를 풀고, 알고리즘을 배우고, 진척도를 추적하도록 도우며, 전반적인 준비 과정 내내 멘티를 지원한다.

각 학생에게는 자신을 제외한 모든 학생 중 정확히 한 명의 멘토가 있으며, 한 사람이 여러 명의 멘토가 될 수 있다. 모든 학생 $i$에 대해, 그 학생이 프로그래밍 대회를 얼마나 잘하는지를 근사하여 나타내는 레이팅 $\mathbf{R_i}$를 알고 있다. 멘토가 멘티보다 훨씬 강해서는 안 된다고 여겨지므로, 학생 $j$가 학생 $i$의 멘토가 될 수 있는 것은 $\mathbf{R_j} \le 2 \times \mathbf{R_i}$인 경우뿐이다. 멘토의 레이팅이 멘티의 레이팅보다 낮거나 같을 수도 있음에 유의하라.

당연하게도, 각 학생은 가능한 한 가장 강한 멘토를 원한다. 각 학생이 선택할 수 있는 멘토의 가능한 최고 레이팅을 구하도록 도와줄 수 있는가?

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{R_i} \le 10^6$.

테스트 세트 1

시간 제한: 20초. $2 \le \mathbf{N} \le 1000$.

테스트 세트 2

시간 제한: 40초. $2 \le \mathbf{N} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 구성된다.

각 테스트 케이스의 첫 번째 줄에는 그룹의 학생 수를 나타내는 정수 $\mathbf{N}$이 주어진다.

각 테스트 케이스의 두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{R_1} \ \mathbf{R_2} \ \mathbf{R_3} \ \dots \ \mathbf{R_N}$가 주어지며, 여기서 $\mathbf{R_i}$는 $i$번째 학생의 레이팅이다.

각 테스트 케이스마다 Case #$x$: $M_1 \ M_2 \ M_3 \ \dots \ M_N$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 (1부터 시작), $M_i$는 $i$번째 학생의 멘토가 가질 수 있는 최대 레이팅이다. 해당 학생에게 적합한 멘토가 없다면 $-1$이다.

예제 케이스 #1에는 레이팅이 $2000$, $1500$, $1900$인 세 명의 학생이 있다. 모든 학생은 다른 어떤 학생이든 멘토로 선택할 수 있으므로, 모두 가능한 최고 레이팅을 가진 멘토를 선택한다. 그 결과, 이들은 각각 레이팅이 $1900$, $2000$, $2000$인 멘토를 선택한다. 이 경우 레이팅이 $2000$인 학생이 다른 두 학생의 멘토가 된다는 점에 유의하라.

예제 케이스 #2에는 레이팅이 $1000$, $600$, $1000$, $2300$, $1800$인 다섯 명의 학생이 있다(일부 학생의 레이팅은 같을 수 있음에 유의하라). 레이팅이 $1000$인 두 학생 모두에 대해, 선택 가능한 멘토 중 레이팅이 가장 높은 멘토의 레이팅은 $1800$이다. $2300 > 2 \times 1000$이므로 레이팅이 $2300$인 멘토를 선택할 수 없다. 레이팅이 $600$인 학생은 레이팅이 $1800$ 또는 $2300$인 멘토를 선택할 수 없으므로, 레이팅이 $1000$인 멘토를 선택한다(레이팅이 $1000$인 두 학생 중 어느 쪽이든 가능하다). 레이팅이 $2300$인 학생은 다른 어떤 학생이든 멘토로 선택할 수 있으므로, 가능한 최고 레이팅인 $1800$의 멘토를 선택한다. 마지막으로 레이팅이 $1800$인 학생도 다른 어떤 학생이든 멘토로 선택할 수 있으므로, 가능한 최고 레이팅인 $2300$의 멘토를 선택한다. 따라서 최종적으로 학생들은 각각 레이팅이 $1800$, $1000$, $1800$, $1800$, $2300$인 멘토를 선택한다.

예제 케이스 #3에는 레이팅이 $2500$와 $1200$인 두 학생이 있다. 레이팅이 $2500$인 학생에게는 레이팅이 $1200$인 다른 학생이 멘토가 될 수 있으며, 다른 선택지는 없다. 레이팅이 $1200$인 학생에게는 $2500 > 2 \times 1200$이므로 레이팅이 $2500$인 멘토를 배정할 수 없으며, 따라서 이 학생에게는 적합한 멘토가 없다. 최종적으로 이 테스트 케이스의 결과로 $1200$와 $-1$를 출력한다.