Problem Description

You are given an array $a$ of length $n$. You must perform exactly $k$ times operations.

For each operation,

$\bullet$ First, you select two integers $l,r$ $($$1\leq l\leq r \leq n$$)$,

$\bullet$ Second, change $a$ to $b$, satisfy :

$\ \ \ \ \circ$ For each $i$ $($$1\le i< l$$)$ , $b_i=a_i$;

$\ \ \ \ \circ$ For each $i$ $($$l\le i< r$$)$ , $b_i=a_{i+1}$;

$\ \ \ \ \circ$ $b_r=a_l$

$\ \ \ \ \circ$ For each $i$ $($$r< i\le n$$)$ , $b_i=a_i$;


Find the lexicographically largest possible array after $k$ times operations.

Array $x$ is lexicographically greater than array $y$ if there exists an index $i$ $($ $1\leq i\leq n$ $)$ such that $x_i$ $>$ $y_i$ and for every $j (1\leq j \lt i) ,$ $ x_j=y_j$.

Input

The first line of the input contains one integer $T$ $($$1\leq T\leq 100$ $)$ --- the number of test cases. Then $T$ test cases follow.

The first line of the test case contains two integers $n,k$ $($$1\le n,k\le 300000$$)$

The second line of the test case contains $n$ integers $a_1,a_2,...,a_n$$($$1\le a_i\le 300000$$)$

The sum of $n$ over all testcases doesn't exceed $10^{6}$.

The sum of $k$ over all testcases doesn't exceed $10^{6}$.

Output

For each testcase,one line contains $n$ integers ,$a_1,a_2,...,a_n$ --- the lexicographically largest possible array after $k$ times operations.

**Don‘t have spaces at the end of the line**

2
7 3
1 4 2 1 4 2 4
5 2
4 3 5 4 5

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