crescator

Enunț

Mihai a fost un elev foarte obraznic la ora de informatică, așa că doamna de informatică i-a dat să rezolve următoarea problema:

Să se spună dacă un șir de N elemente poate deveni crescător, aplicând de câte ori vrei operația $“inter-K”$

Definim operația $“inter-K”$ astfel:

• Există $i$ și $j$, $1 \leq i, j \leq N$, $i \neq j$
• Dacă $a_i \equiv a_j$ (mod $K$), atunci se pot interschimba valorile $a_i$ și $a_j$

Ajutați-l pe Mihai să rezolve problema.

Cerință

Dându-se cele 2 numere naturale $N$ și $K$, apoi $N$ numere naturale cu propietatea din enunț, să se afișeze mesajul $DA$, dacă șirul poate deveni crescător, respectiv $NU$, dacă șirul nu poate deveni crescător.

Date de intrare

În fișierul de intrare crescator.in, pe prima linie se vor afla 2 numere naturale, acestea reprezentând N, respectiv K. Pe următoarea linie se vor afla N numere naturale, acestea reprezentând șirul pe care doamna voastră de informatică vi l-a acordat.

Date de ieșire

In fișierul de ieșire crescator.out, pe prima linie se va afla mesajul $DA$, dacă șirul poate deveni crescător, respectiv $NU$, dacă șirul nu poate deveni crescător

Restricții si precizări:

• $1 \leq N \leq 150.000$
• $1 \leq K \leq 60$
• $1 \leq a_i \leq 80.000, 1 \leq i \leq N$
• Pentru 20 de puncte, $N \leq 5.000$ si $K=2$
• Pentru inca 20 de puncte, $N \leq 5.000$
• Pentru inca 20 de puncta, $K \leq 5$
• În enunț se specifică ca șirul să fie $crescător$, deci și șirurile 1 1 1 și 1 2 2 se iau în considerare ca șiruri crescătoare, de exemplu

Exemplu:

crescator.in

5 4
6 11 2 3 7

crescator.out

DA

Explicații:

În șirul 6, 11, 2, 3, 7, putem aplica de 3 ori operația $"inter-K"$, astfel:
interschimbăm valorile 2 si 6, deoarece $2 \equiv 6$ (mod $4$), rezultând șirul 2, 11, 6, 3, 7,
apoi interschimbăm valorile 11 si 3, deoarece $11 \equiv 3$ (mod $4$), rezultând sirul 2, 3, 6, 11, 7,
apoi interschimbăm valorile 11 si 7, deoarece $11 \equiv 7$ (mod $4$), rezultând sirul 2, 3, 6, 7, 11, acesta fiind un șir crescător.
Atenție! Aceasta nu e singura metodă de a ajunge la un șir crescător, dar e cea mai eficientă