Гра з монетами

Для гри з монетами використовується горизонтальна полоска, розділена на N одинакових квадратних клітинок. На початку у деяких клітинках дошки є монети, а у деяких - ні.

Два гравці - Дмитро та Іван - починають по черзі робити ходи, причому Дмитро ходить першим. За один хід гравець може виконати наступні дії:

1. Вибрати довільну монету, праворуч від якої є хоча б одна вільня клітинка.

2. Перемістити вибрану монету у довільну із вільних клвтинок, які знаходять праворуч від неї.

3. Перемістити рівно на одну клітинку ліворуч всі монети, які знаходяться між позиціями вибраної монети до і після її переміщення.

Приклад ходу проілюстровано на наступному рисунку:

Якщо позначити монету символом 'C', а пусту клітинку - символом '.', то стан полоски можна описати як рядок з N символів. Для прикладу вище стан полоски до ходу описується рядком "C.CC...C..CC.C", а після ходу - рядком "C.C...C..CC.CC".

Програвшим вважається той гравець, який не зміг зробити хід (тобто на момент ходу цього гравця всі монети примикають до правого краю полоски). Відповідно, гравець, який зробив самий останній хід - це переможець гри.

Припустимо, що Дмитро та Іван грають у описану гру оптимально. Напишіть програму, яка отримує на вхід опис початкового стану полоски і визначає переможця гри.

Вхідні дані

Рядок S, який описує стан полоски до початку гри.

1. Рядок S містить віт 2 до 100 символів включно.

2. Рядок S може містити лише символи 'C' і '.'.

3. Рядок S містить хоча б одне входженння символу 'C'.

4. Рядок S містить хоча б однк входження символу '.'.

Вихідні дані

Рядок, рівний "DMITRY", якщо переможцем гри виявиться Дмитро, і рівний "IVAN", якщо переможцем гри стане Іван.

Приклади