Sort

Fie $A$ un șir de $N$ numere naturale. Construiți un șir $B$ de $N$ numere naturale care respectă următoarele proprietăți:

• Pentru toți $1 \leq i \leq N − 1, B[i] \leq B[i + 1]$.
• Pentru toți $1 \leq i \leq N, B[i]$ poate fi obținut din $A[i]$ printr-un număr de permutări circulare ale cifrelor lui $A[i]$. Acest număr poate fi $0$, în acest caz $B[i] = A[i]$.

Operația de permutare circulară mută toate cifrele, în afară de prima, cu o poziție spre stânga și aduce prima cifră pe ultima poziție. De exemplu, din numărul $12345$ putem obține, printre altele, numerele $34512$ și $51234$ folosind permutări circulare, dar nu putem obține numărul $14325$.

Se garantează că pentru toți $1 \leq i \leq N, A[i]$ nu conține cifra $0$.

Date de intrare

Prima linie va conține numărul $N$. A doua linie va conține șirul $A$, constând din $N$ numere naturale separate prin câte un spațiu.

Date de ieșire

Dacă nu există niciun șir $B$ care respectă proprietățile din enunț , afișați cuvântul NU pe prima linie. Altfel, afișați cuvântul DA pe prima linie. Pe a doua linie afișați orice șir $B$ care respectă proprietățile din enunț.

Restricții și precizări

• Pentru toate subtask-urile, $1 \leq A[i] \leq 10^8$
• Trebuie să rezolvați corect toate testele din cadrul unui subtask pentru a primi punctajul aferent acestuia.

Exemplul 1

sort.in

3
2435 2134 1135

sort.out

DA
2435 3421 3511

Exemplul 2

sort.in

3
511 765 4

sort.out

NU

Explicație

În al doilea exemplu, $B[2]$ poate fi $765, 657$ sau $576$, dar niciuna din aceste variante nu este mai mică sau egală cu $4$.