Game with Coins

In the coin game, a horizontal strip is divided into N identical square cells. Initially, some of these cells contain coins, while others are empty.

Two players, Dmytro and Ivan, take turns making moves, with Dmytro going first. During each turn, a player can perform the following actions:

1. Choose any coin that has at least one empty cell to its right.

2. Move the selected coin to any empty cell located to its right.

3. Shift all coins that lie between the selected coin's original and new positions exactly one cell to the left.

An example move is shown in the following images:

In this game, a coin is represented by the symbol 'C', and an empty cell by the symbol '.'. Thus, the state of the strip can be described as a string of N characters. For the example above, the strip's state before the move is represented by the string "C.CC...C..CC.C", and after the move, it becomes "C.C...C..CC.CC".

The player who cannot make a move (i.e., when all coins are adjacent to the right edge of the strip during their turn) loses the game. Consequently, the player who made the last move wins.

Assuming both Dmytro and Ivan play optimally, write a program that takes the initial state of the strip as input and determines the winner of the game.

Input

A string S that describes the initial state of the strip.

1. The string S contains between 2 and 100 characters, inclusive.

2. The string S consists only of the characters 'C' and '.'.

3. The string S contains at least one 'C'.

4. The string S contains at least one '.'.

Output

Output "DMITRY" if Dmytro wins the game, or "IVAN" if Ivan wins.

Examples