학생과 멘토

구글의 Kick Start, Code Jam 같은 프로그래밍 대회를 앞두고 $N$명의 학생이 함께 준비한다. 서로 돕기 위해 각 학생은 다른 학생 중에서 멘토를 한 명 고른다. 멘토는 멘티가 문제를 풀고, 알고리즘을 배우고, 진도를 점검하는 등 준비 과정 전반을 돕는다.

각 학생은 다른 모든 학생 중에서 정확히 한 명의 멘토를 고르며, 한 사람이 여러 명의 멘티에게 멘토가 될 수 있다. 모든 학생 $i$에게는 대회에서의 실력을 대략 나타내는 레이팅 $R_i$가 주어진다. 멘토가 멘티보다 지나치게 강해서는 안 된다고 보므로, 학생 $j$는 $R_j \le 2 \times R_i$일 때에만 학생 $i$의 멘토가 될 수 있다. 멘토의 레이팅은 멘티와 같거나 낮아도 된다.

각 학생은 가능한 한 강한 멘토를 원한다. 각 학생에 대해 고를 수 있는 멘토 레이팅의 최댓값을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다.

각 테스트 케이스의 첫 줄에는 학생의 수 $N$이 주어진다.

둘째 줄에는 $N$개의 정수 $R_1, R_2, \dots, R_N$이 공백으로 구분되어 주어진다. $R_i$는 $i$번째 학생의 레이팅이다.

각 테스트 케이스마다 Case #x: M1 M2 M3 ... MN 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $M_i$는 $i$번째 학생의 멘토가 가질 수 있는 레이팅의 최댓값이다. 조건에 맞는 멘토가 없는 학생에게는 $-1$을 출력한다.

• $1 \le T \le 100$.
• 모든 $i$에 대해 $1 \le R_i \le 10^6$.