Для игры с монетами используется горизонтальная полоска, разделенная на N одинаковых квадратных клеток. Изначально в некоторых клетках доски есть монеты, а в некоторых - нет.
Два игрока - Дмитрий и Иван - начинают по очереди делать ходы, причем Дмитрий ходит первым. За один ход игрок может проделать следующие действия:
Выбрать любую монету, справа от которой есть хотя бы одна свободная клетка.
Переместить выбранную монету в любую из свободных клеток, находящихся справа от нее.
Переместить ровно на одну клетку влево все монеты, которые находятся между позициями выбранной монеты до и после ее перемещения.
Пример хода проиллюстрирован на следующем рисунке:
Если обозначить монету символом 'C', а пустую клетку - символом '.', то состояние полоски можно описать как строку из N символов. Для примера выше состояние полоски до хода описывается строкой "C.CC...C..CC.C", а после хода - строкой "C.C...C..CC.CC".
Проигравшим считается тот игрок, который не смог сделать ход (т.е. к моменту хода этого игрока все монеты примыкают к правому краю полоски). Соответственно, игрок, сделавший самый последний ход - это победитель игры.
Предположим, что Дмитрий и Иван играют в описанную игру оптимально. Напишите программу, получающую на вход описание начального состояния полоски и определяющую победителя игры.
Строка S, описывающая состояние полоски до начала игры.
Строка S содержит от 2 до 100 символов включительно.
Строка S может содержать только символы 'C' и '.'.
Строка S содержит хотя бы одно вхождение символа 'C'.
Строка S содержит хотя бы одно вхождение символа '.'.
Строка, равная "DMITRY", если победителем игры окажется Дмитрий, и равная "IVAN", если победителем игры станет Иван.