Relief

Planeta Altair IV prezintă un interes ridicat datorită reliefului său divers, asftel că nava USS Enterprise se află în orbita sa într-o misiune de cercetare. După câteva zile de recoltare de date, șeful departamentului de științe, Spock, observă că formele de relief, ale căror curbe de înalțime sunt codificate prin numere, se împart în două categorii: munți și pante. Există și forme de relief care nu aparțin niciuneia dintre categoriile precizate.

Un munte este o formă de relief codificată printr-un număr ale cărui cifre se află în ordine strict crescătoare până la o anumită cifră $v$, urmând ca după aceasta cifrele să apară în ordine strict descrescătoare. De exemplu, numărul $123432$ codifică un munte.

O pantă ascendentă este o formă de relief codificată printr-un număr ale cărui cifre se află în ordine strict crescătoare. De exemplu, numărul $123$ codifică o pantă ascendentă.

O pantă descendentă este o formă de relief codificată printr-un număr ale cărui cifre se alfă în ordine strict descrescătoare. De exemplu, numărul $321$ codifică o pantă descendentă.

Pentru a-și putea scrie raportul despre descoperirile misiunii, Spock trebuie să răspundă următoarelor întrebări:

1. În ce categorie se încadrează fiecare formă de relief identificată?
2. Care dintre formele de relief care nu aparțin niciunei categorii ar putea, prin eliminarea unei curbe de nivel, să devină munte?

Totuși, în mod neașteptat, nava este atacată de klingoniei, iar comandantul Spock este chemat pe punte. Responsabilitatea răspunderii la întrebările pentru raportul misiunii este acum în mâinile voastre.

Cerință

Dându-se $n$ numere naturale, să se afișeze:

1. Pentru fiecare număr:
   • caracterul $m$, dacă numărul reprezintă un munte;
   • caracterul $a$, dacă numărul reprezintă o pantă ascendentă;
   • caracterul $d$, dacă numărul reprezintă o pantă descendentă;
   • caracterul $x$, altfel.
2. Numerele care nu reprezintă munți deja și, prin eliminarea unei singure cifre, ar putea deveni munți, în ordinea în care apar în datele de intrare.

Date de intrare

Fișierul de intrare relief.in conține pe prima linie valoarea numărului natural $n$.
Pe a doua linie se află un număr natural $c$, cu valoarea între $1$ și $2$, reprezentând numărul întrebării la care se răspunde.
Pe a treia linie se află $n$ numere, separate prin spațiu, reprezentând formele de relief identificate.

Date de ieșire

Dacă $c = 1$, se vor afișa $n$ caractere separate prin spațiu, caracterul de pe poziția $i$ reprezentând categoria formei de relief de pe poziția $i$ din șir.

Dacă $c = 2$, se vor afișa numerele reprezentând formele de relief care pot deveni, prin eliminarea unei cifre, munți. Ordinea în care acestea se vor afișa este ordinea în care apar în șirul inițial.

Restricții și precizări

• $c$ poate avea valorile $1$ sau $2$;
• $1 \leq n \leq 10 \ 000$;
• Numerele citite sunt numere naturale cu maxim $9$ cifre;
• Numerele de o singură cifră nu sunt considerate pante;
• Pentru $c = 1$ se vor acorda 50 de puncte;
• Pentru $c = 2$ se vor acorda 50 de puncte;
• Pentru 20 de puncte, $c = 1$ și numerele citite reprezintă doar pante sau forme de relief nespecificate;
• Pentru $c = 2$ se garantează că există cel puțin un număr ce poate deveni munte prin ștergerea unei cifre.

Exemplul 1

relief.in

6
1
123 143 1092 432 1231 9

relief.out

a m x d m x

Explicație

• $123$ este de tip pantă ascenentă (are toate cifrele în ordine crescătoare) $\Rightarrow$ se afișează $a$
• $143$ este un număr de tip munte (cifrele sunt în ordine crescătoare până la cifra $4$, apoi scad) $\Rightarrow$ se afișează $m$
• $1092$ nu este nici pantă, nici munte $\Rightarrow$ se afișează $x$
• $432$ este de tip pantă descendentă (are toate cifrele în ordine descrescătoare) $\Rightarrow$ se afișează $d$
• $1231$ este de tip munte (cifrele sunt în ordine crescătoare până la cifra $3$, apoi scad) $\Rightarrow$ se afișează $m$

Exemplul 2

relief.in

8
2
123 143 1092 432 1231 123321 579649 70012542

relief.out

1092 123321 579649 70012542

Explicație

• Putem șterge cifra $0$ din $1092$ pentru a obține numărul $192$, care este un număr de tip munte.
• Putem șterge una din cifrele $3$ din $123321$ pentru a obține numărul $12321$, care este un număr de tip munte.
• Putem șterge ultima cifră $9$ din $579649$ pentru a obține numărul $57964$, care este un număr de tip munte.
• Putem șterge cifra $7$ din $70012542$ pentru a obține numărul $12542$, care este un număr de tip munte.