Fie un vector de numere naturale *A[]* ce contine *N* elemente. O sortare in zig-zac de ordin *k* se defineste in felul urmator:

a1 >= a2 >= ... >= ak >= ak+1

a{~1~} ≥ a{~2~} ≥ ... ≥ a{~k~} ≥ a{~k+1~}

ak+1 <= ak+2 <= ... <= a2*k+1

a{~k+1~} ≤ a{~k+2~} ≤ ... ≤ a{~2*k+1~}

a2*k+1 >= a2*k+2 >= ... >= a3*k+1

a{~2*k+1~} ≥ a{~2*k+2~} ≥ ... ≥ a{~3*k+1~}

si asa mai departe.

si asa mai departe, adica :
primele _*k*_ elemente trebuie sa fie in ordine necrescatoare
elementele de la pozitiile _*k + 1*_ pana la _*2 * k + 1*_ trebuie sa fie in ordine nedescrescatoare
 
In general:
 
elementele de la pozitiile _*p * k + 1*_ pana la _*(p + 1) * k + 1*_ trebuie sa fie in ordine necrescatoare daca _*p*_ este par si nedescrescatoare daca _*p*_ este impar.
 
Pentru a rezolva problema trebuie sa implementati o astfel de sortare dar care sa foloseasca interschibari doar de elemente care sunt pe pozitii consecutive (swap *A[i]* si *A[i+1]*).
 

h2. Date de intrare

Fişierul de intrare $zigsort.in$ ...

Fişierul de intrare $zigsort.in$ contine pe prima linie un numar natural *T* reprezentand numarul de teste urmat de descrierile fiecarui test:
Pe prima linie numerele *N* si *K* separate printr-un spatiu.
Pe urmatoarea linie *N* numere naturale, valorile initiale ale vectorului *A[]*.

h2. Date de ieşire

În fişierul de ieşire $zigsort.out$ ...

În fişierul de ieşire $zigsort.out$ afisati pentru fiecare test, pe cate o linie, interschimarile de tipul celor descrise care sorteaza vectorul *A[]* transformandu-l intr-un vector zigsortat de ordin *K*.
Primul numar reprezinta numarul M de interschimbar necesare iar urmatoarele M numere reprezinta indici *i* pentru care se apeleaza *swap(A[i], A[i+1])*, in ordinea din fisierul de iesire astfel incat la final sa avem rezultatul dorit.

h2. Restricţii

* $... ≤ ... ≤ ...$

* 2 ≤ N ≤... ≤ ...$

h2. Exemplu