Students and Mentors

A group of $N$ students prepares together for upcoming programming competitions such as Kick Start and Code Jam by Google. To help each other prepare, each student picks a mentor among the other students. A mentor helps their mentee solve problems, learn algorithms, track progress, and support them throughout preparation.

Each student has exactly one mentor among all other students, and one person can be a mentor to several students. Each student $i$ has a rating $R_i$ that approximates how strong they are at programming competitions. A mentor should not be much stronger than their mentee, so student $j$ can be the mentor of student $i$ only if $R_j \le 2 \times R_i$. A mentor may have a rating lower than or equal to their mentee's rating.

Each student wants the strongest possible mentor. For each student, find the highest rating of a mentor they can pick.

The first line contains the number of test cases $T$. Each of the $T$ test cases follows on two lines.

The first line of each test case contains the number of students $N$.

The second line contains $N$ integers $R_1, R_2, \dots, R_N$, separated by spaces. $R_i$ is the rating of the $i$-th student.

For each test case, print one line in the form Case #x: M1 M2 M3 ... MN. Here $x$ is the test case number starting from 1, and $M_i$ is the highest rating of a mentor the $i$-th student can have. If the $i$-th student has no suitable mentor, print $-1$ for that student.

• $1 \le T \le 100$.
• $1 \le R_i \le 10^6$ for all $i$.