Monet oyunu

Oyun üçün sikkələrlə üfüqi zolaq istifadə olunur, N eyni kvadrat hüceyrəyə bölünmüşdür. Başlanğıcda bəzi hüceyrələrdə sikkələr var, bəzilərində isə yoxdur.

İki oyunçu - Dmitri və İvan - növbə ilə hərəkət edirlər, Dmitri birinci başlayır. Bir hərəkət zamanı oyunçu aşağıdakı addımları ata bilər:

1. Sağında ən azı bir boş hüceyrə olan istənilən sikkəni seçmək.

2. Seçilmiş sikkəni sağında olan boş hüceyrələrdən birinə köçürmək.

3. Seçilmiş sikkənin köçürülmədən əvvəlki və sonrakı mövqeləri arasında olan bütün sikkələri bir hüceyrə sola köçürmək.

Hərəkət nümunəsi aşağıdakı şəkildə göstərilmişdir:

Əgər sikkəni 'C', boş hüceyrəni isə '.' simvolu ilə işarələsək, zolağın vəziyyətini N simvoldan ibarət bir sıra kimi təsvir etmək olar. Yuxarıdakı nümunədə hərəkətdən əvvəl zolağın vəziyyəti "C.CC...C..CC.C" sırası ilə təsvir olunur, hərəkətdən sonra isə "C.C...C..CC.CC" sırası ilə.

Hərəkət edə bilməyən oyunçu məğlub hesab olunur (yəni, bu oyunçunun hərəkət anında bütün sikkələr zolağın sağ kənarına bitişikdir). Beləliklə, sonuncu hərəkəti edən oyunçu oyunun qalibi olur.

Tutaq ki, Dmitri və İvan təsvir olunan oyunu optimal oynayırlar. Proqram yazın ki, zolağın başlanğıc vəziyyətini daxil edərək oyunun qalibini müəyyən etsin.

Giriş verilənləri

Oyunun başlanğıc vəziyyətini təsvir edən S sırası.

1. S sırası 2 ilə 100 simvol arasında ola bilər.

2. S sırası yalnız 'C' və '.' simvollarını ehtiva edə bilər.

3. S sırası ən azı bir 'C' simvolu ehtiva edir.

4. S sırası ən azı bir '.' simvolu ehtiva edir.

Çıxış verilənləri

Oyunun qalibi Dmitri olarsa, "DMITRY" sırası, İvan qalib olarsa, "IVAN" sırası.

Nümunələr