Problem E: Bubble sort

Problem E: Bubble sort

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 680  Solved: 198
[Submit][Status][Web Board]

Description

Ella has a sequence of n integers. After she learns the 'Bubble sort'(in ascending order), she wants to implement this algorithm. The question is what the sequence looks like after K times 'Bubble operation'. One 'Bubble operation' is like this:

for(int i = 1; i < n; ++i) { if(a[i] > a[i + 1]) swap(a[i], a[i + 1]); }

The sequence starts from 1, and its length is n.

Input

The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be two integers n and K(1 <= K <= n <= 200000). The second line will be n integers, a1……an(1 <= ai <= 109), representing the original sequence. It queries what the sequence is like after K times 'Bubble sort' from the original sequence.

Output

For each query, print the sequence in one line, do not print extra space at the end of one line.

Sample Input

1
5 1
5 4 3 2 1

Sample Output

4 3 2 1 5

HINT

[Submit][Status]