Reordnr

Cerință

Fie numărul de teste $T$, un număr natural. Pentru fiecare test se dau două numere naturale, $C$ și $N$, urmate de un șir de $N$ cifre nenule. Dacă:

• $C=1$ atunci să se reordoneze cifrele din șir astfel încât să formeze un palindrom sau să se afișeze $−1$ dacă nu e posibil;
• $C=2$ atunci să se reordoneze cifrele din șir astfel încât oglinditul noului șir să difere pe exact o poziție față de șirul reordonat sau să se afișeze $−1$ dacă nu e posibil;
• $C=3$ atunci să se reordoneze cifrele din șir astfel încât oglinditul noului șir să difere pe exact două poziții față de șirul reordonat sau să se afișeze $−1$ dacă nu e posibil.

Date de intrare

Fișierul de intrare reordnr.in conține:

• pe prima linie un număr natural $T$, cu semnificația din enunț;
• pe următoarele $T$ linii, câte două numere naturale, $C$ și $N$, și, pe aceeași linie, $N$ cifre nenule.

Date de ieșire

Afișează în reordnr.in, pe $T$ linii, răspunsul la fiecare test.

Restricții și precizări

• $1 \leq T \leq 10^{4}$;
• $1 \leq N \leq 10^{6}$;

Observație: suma tuturor $N$-urilor este mai mică sau egală cu $10^{6}$.

Exemplu

reordnr.in

6
1 4 2 1 2 1
1 8 1 2 3 1 2 3 4 5
2 4 2 9 2 1
2 5 2 9 1 9 2
3 4 2 3 2 1
3 4 2 1 2 1

reordnr.out

1 2 2 1
-1
-1
-1
2 1 3 2
-1