Igra

Έχοντας λύσει την κουραστική εργασία, ο Mirko αποφάσισε να παίξει ένα παιχνίδι με τον καλό του φίλο Slavko.
Έχουν γράψει μια ακολουθία από \(Ν\) γράμματα σε ένα χαρτί. Καθένας από αυτούς προσπαθεί να συνθέσει μια λέξη χρησιμοποιώντας γράμματα από την ακολουθία. Εναλλάσσονται σειρές που αποτελούνται από την αφαίρεση ενός μόνο γράμματος από την ακολουθία και την προσθήκη του στο τέλος της λέξης τους. Ο Mirko έχει την πρώτη σειρά. Το παιχνίδι τελειώνει όταν δεν υπάρχουν γράμματα στην ακολουθία.
Ορίζουμε μια λέξη να είναι πιο όμορφη από μια άλλη λέξη αν έρχεται πρώτη αλφαβητικά. Ο παίκτης που έχει την πιο όμορφη λέξη στο τέλος του παιχνιδιού κερδίζει. Αν και οι δύο παίκτες έχουν ίσες λέξεις, χάνουν και οι δύο.
Ο Mirko είναι πολύ καλύτερος παίκτης από τον Slavko, επομένως αποφάσισε να διευκολύνει τον Slavko επιλέγοντας πάντα το πιο δεξί γράμμα που απομένει στην ακολουθία. Γνωρίζοντας αυτό, ο Slavko θέλει να μάθει αν είναι δυνατόν να κερδίσει και ποια είναι η πιο όμορφη λέξη με την οποία μπορεί να τελειώσει το παιχνίδι.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν άρτιο θετικό ακέραιο ~N\;(2 \leq N \leq 100\,000)~.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ χαρακτήρες, την αρχική ακολουθία γραμμάτων. Όλοι οι χαρακτήρες είναι πεζά γράμματα από το αγγλικό αλφάβητο.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει "DA" εάν είναι δυνατό να κερδίσει ο Slavko, και "NE" διαφορετικά.

Η δεύτερη γραμμή εξόδου πρέπει να περιέχει την πιο όμορφη λέξη που μπορεί να έχει ο Slavko στο τέλος του παιχνιδιού.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~50~% των συνολικών πόντων, ο αριθμός ~N~ δεν θα υπερβαίνει το ~1000~.

Παραδείγματα

input

2
ne

output

NE
n

input

4
kava

output

DA
ak

input

8
cokolada

output

DA
acko