Sacrifice

Given an array $a$ of length $n$ and parameters $m$ and $k$, you can perform any number of swaps in the array. After the operations (possibly zero operations), we cycle the array (repeat it an infinite number of times). Among all the arrays that you can achieve, output one that maximizes the value below:

For example, for a = [1,2,3,4], we consider a_5 = 1 and a_6 = 2, and so on.

Input

The first line contains a single integer $t$ (1 \le t \le 10) -- the number of test cases.

The first line of each test case contains three integers $n$, $m$, $k$ (1 \le m \le n \le 10^5, 1 \le k \le 10^9).

The second line of each test case contains $n$ space-separated integers a_1, a_2, \dotsc, a_n (1 \le a_1, a_2, \dotsc, a_n \le 10^9) -- the array $a$.

It is guaranteed that the sum of $n$ for all tests does not exceed 2 \cdot 10^5.

Output

Output any valid permutation of $a$ that maximizes the value.

Note

In the first test case, one of the optimal sums will consist of the following bold numbers [3,[**4,9,5**],1], which gives \max(f) = 18.

In the second test case, one of the optimal sums will consist of the following red numbers:[**2_{(2)},1_{(3)},3_{(1)}**], which gives \max(f) = 6.

In the third test case, one of the optimal sums will consist of the following red numbers (according to the cyclic pattern):

1. [6,3,2,**10**], total sum $10$, and we summed $1$ element so far.

2. [**6,3,2,10**], total sum $31$, and we summed $5$ elements so far.

3. [**6,3,2,10**], total sum $52$, and we summed $9$ elements so far.

4. [**6,3,2,10**], total sum $73$, and we summed $13$ elements so far.

5. [**6,3,2,10**], total sum $94$, and we summed $17$ elements so far.

This gives \max(f)=94.

Scoring

1. (5 points): m+k-1 \le n

2. (10 points): 1 \le k \le n \le 10

3. (10 points): 1 \le k \le n \le 500

4. (15 points): m=1

5. (20 points): a_i \le 2

6. (40 points): no additional constraints.