Given a sequence $a_i$ of $n$ integers (indexed $1 \sim n$), for each prefix $a_1, a_2, \dots, a_k$ ($1 \le k \le n$), consider all non-empty subsets $S \subseteq \{1, 2, \dots, k\}$. Define $f(S) = \min\{a_i \mid i \in S\} + \max\{a_i \mid i \in S\}$.

For each prefix of the sequence $a$, among the corresponding $2^k - 1$ possible cases, find the mode of the values of $f(S)$ (the value that appears most frequently). If there are multiple values that appear with the same maximum frequency, output the largest among them.

Input

The first line contains an integer $t$ ($1 \le t \le 1000$), representing the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \le n \le 10^6$), representing the number of integers.

The next line contains $n$ integers representing $a_i$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single line containing $n$ space-separated integers, representing the largest mode of the values of $f(S)$ for each prefix, respectively.

Examples

Input 1

3
6
1 1 4 5 1 4
5
1 2 3 4 5
5
1 2 2 1 2

Output 1

2 2 5 6 6 6
2 4 4 5 6
2 4 4 3 3

Note

For the first example: For the first 1 number, 2 appears 1 time, the largest mode is 2. For the first 2 numbers, 2 appears 3 times, the largest mode is 2. For the first 3 numbers, 2 appears 3 times, 5 appears 3 times, 8 appears 1 time, the largest mode is 5. For the first 4 numbers, 2 appears 3 times, 5 appears 3 times, 6 appears 6 times, 8 appears 1 time, 9 appears 1 time, 10 appears 1 time, the largest mode is 6. For the first 5 numbers, 2 appears 7 times, 5 appears 7 times, 6 appears 14 times, 8 appears 1 time, 9 appears 1 time, 10 appears 1 time, the largest mode is 6. For the first 6 numbers, 2 appears 7 times, 5 appears 21 times, 6 appears 28 times, 8 appears 3 times, 9 appears 3 times, 10 appears 1 time, the largest mode is 6.