lexicografic

Se dă un șir $v$ format din $N$ elemente naturale nenule nu neapărat distincte. Asupra șirului putem aplica un singur tip de operație: interschimbarea a două elemente aflate pe poziții consecutive.

Cerință

Dându-se un număr natural $K$, se cere șirul minim lexicografic ce se poate obține prin aplicarea a cel mult $K$ interschimbări de elemente de pe poziții consecutive.

Date de intrare

În fișierul lexicografic.in se află pe prima linie $T$, reprezentând numărul de teste. Urmează cele $T$ teste, fiecare pe câte 2 linii. Pe prima linie din cadrul unui test se află două numere $N$ și $K$ separate prin spațiu. Pe linia a doua din cadrul unui test se află cele $N$ elemente ale șirului separate prin spații.

Date de ieșire

În fișierul lexicografic.out se vor afișa cele $T$ linii, câte una corespunzătoare răspunsului pe fiecare test. Linia corespunzătoare unui test va conține cele $N$ elemente separate prin spații ale șirului minim lexicografic ce s-a obținut din șirul inițial, după aplicarea a cel mult $K$ interschimbări de elemente de pe poziții consecutive.

Restricții și precizări

• $1 ≤ N ≤ 250 \ 000$;
• $T ≤ 2 \ 500$;
• într-un fișier de intrare suma totală a lungimilor şirurilor corespunzătoare celor $T$ teste nu va depăși $250 \ 000$;
• $1 ≤ K ≤ N \cdot (N-1)/2$;
• $1 ≤ v[i] ≤ N$, pentru $1 ≤ i ≤ N$;
• Vă rugăm să acordați atenție tipului de date necesar pentru a citi valorea lui $K$;
• Pentru acordarea punctajului pe un fișier de test este necesară rezolvarea corectă a tuturor celor $T$ teste;
• Pentru teste în valoare de $5$ puncte se garantează $K = N \cdot (N – 1) / 2$;
• Pentru alte teste în valoare de $7$ puncte se garantează $K = 1$;
• Pentru alte teste în valoare de $23$ de puncte se garantează $T ≤ 10, N ≤ 50$;
• Pentru alte teste în valoare de $4$ puncte se garantează $T ≤ 10, N ≤ 100$;
• Pentru alte teste în valoare de $12$ puncte se garantează $T ≤ 10, N ≤ 500$;
• Pentru alte teste în valoare de $24$ de puncte se garantează $T ≤ 10, N ≤ 2 \ 000$;
• Un șir $a_1,a_2,...,a_n$ este mai mic lexicografic decât un alt șir $b_1,b_2,...,b_n$ dacă există un număr întreg p mai mic sau egal cu N astfel încât: $a_1 = b_1, a_2 = b_2, ... , a_{p–1} = b_{p–1}$, iar $a_p < b_p$.

Exemplu

lexicografic.in

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

lexicografic.out

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

Explicații

Pentru primul test:
Șirul este format din $N = 5$ elemente, și anume $v=(4,2,3,1,1)$. Putem efectua $K=2$ interschimbări. Interschimbând elementele $v[1]$ și $v[2]$ obținem șirul $(2,4,3,1,1)$, apoi după interschimbarea elementelor $v[3]$ și $v[2]$ se obține șirul minim lexicografic $(2,3,4,1,1)$.