Sau khi hoàn thành bài tập tẻ nhạt, Mirko quyết định chơi một trò chơi với người bạn tốt của mình là Slavko. Họ đã viết một chuỗi ~N~ chữ cái trên một tờ giấy. Mỗi người đang cố gắng tạo thành một từ bằng cách sử dụng các chữ cái từ chuỗi. Họ sẽ lần lượt thực hiện các lượt chơi, bao gồm việc loại bỏ một chữ cái khỏi chuỗi và thêm nó vào cuối từ của mình. Mirko sẽ bắt đầu trước. Trò chơi sẽ kết thúc khi không còn chữ cái nào trong chuỗi.

Chúng ta định nghĩa một từ là đẹp hơn từ khác nếu nó xuất hiện trước theo thứ tự bảng chữ cái. Người có từ đẹp hơn vào cuối trò chơi sẽ chiến thắng. Nếu cả hai người có từ giống nhau, họ sẽ đều thua.

Mirko là một người chơi giỏi hơn nhiều so với Slavko, vì vậy cậu đã quyết định tạo điều kiện cho Slavko bằng cách luôn chọn chữ cái bên phải còn lại trong chuỗi. Biết điều này, Slavko muốn tìm hiểu xem liệu có khả năng nào để cậu thắng hay không và từ đẹp nhất mà cậu có thể kết thúc trò chơi là gì.

Yêu cầu: Hãy xác định xem Slavko có thể thắng hay không và tìm từ đẹp nhất mà Slavko có thể tạo ra.

Input

• Dòng đầu tiên của đầu vào chứa một số nguyên dương chẵn ~N~ (~2 \le N \le 10^5~).
• Dòng thứ hai của đầu vào chứa ~N~ ký tự, là chuỗi chữ cái ban đầu. Tất cả các ký tự đều là các chữ cái thường từ bảng chữ cái tiếng Anh.

Output

• Dòng đầu tiên của đầu ra phải chứa “DA” nếu có khả năng để Slavko thắng, và “NE” nếu không.
• Dòng thứ hai của đầu ra phải chứa từ đẹp nhất mà Slavko có thể có khi kết thúc trò chơi.