SOLINFO.ro Runda 3 | Prăjituri

Enunț

Pentru a sărbători reușitele celor calificați la etapele județene ale olimpiadelor de anul acesta, elevii unei clase au decis să comande prăjituri la ora de dirigenție. O clasă este formată din $N$ elevi, iar fiecare își va exprima opinia față de exact două prăjituri din cele $M$ existente la cofetăria de lângă liceu. Fiecare elev își exprimă opinia față de prăjituri astfel: "+ x", dacă îi place prăjitura $x$, respectiv "- x", dacă nu îi place prăjitura $x$ (unde $x$ este un număr de la $1$ la $M$).

Cerință

Aflați ce prăjituri vor fi comandate astfel încât măcar una dintre preferințele fiecărui elev să fie îndeplinită. Dacă o asemenea comandă nu poate fi stabilită, elevii nu vor mai cumpăra prăjituri.

Date de intrare

Pe prima linie se vor afla două numere naturale nenule, $N$ și $M$. Pe următoarele $N$ linii se vor afla cele două preferințe ale elevului curent, sub forma "+ x" (îi place prăjitura $x$) sau "- x" (nu îi place prăjitura $x$).

Date de ieșire

Pe prima linie se vor afișa $M$ răspunsuri. Fiecărei prăjituri îi va corespunde DA (dacă prăjitura va fi comandată) sau NU (dacă prăjitura nu va fi comandată).

Restricții și precizări

• $1 \leq N, M \leq 10^{5}$
• $1 \leq x \leq M$, pentru orice prăjitură.
• Dacă elevii nu vor comanda prăjituri, se va afișa $-1$.
• Soluția nu este unică.

Exemplu

stdin

7 6
+ 4 + 6
+ 3 + 2
- 6 + 5
+ 2 + 6
- 1 - 6
- 3 + 5
+ 1 + 2

stdout

DA DA DA DA DA NU