C. Инна Дима 2

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Инна, Дима хоёр дэлгүүрээс $n x m$ хэмжээтэй хөлөг худалдан авчээ. Энэ хөлгийн бүх нүд нь $D$, $I$, $M$, $A$ үсгүүдийн аль нэгийг нь агуулна аа.

Инна Димад хайртай болохоор уг хөлөг дээгүүр дараах дүрмийг дагаж түүний нэрийг үүсгэж явахыг хүсч байгаа.

  1. Эхлээд аль нэг $D$ үсэгтэй нүдийг сонгож авна.
  2. Үүний дараа аль нэг хөрш $I$, тэгээд $M$, $I$ үсэгтэй нүднүүдрүү шилжиж хайртынхаа нэрийг үүсгэнэ.
  3. Үүний дараа Инна аль нэг хөрш $D$ үсэгтэй нүдрүү шилжиж, дахиад л үйлдлээ давтана. Ингэж Димагийн нэрийг олон дахин үүсгэх юм.

Инна эхлэх нүдээ яаж сонгосноос хамаарч хайртынхаа нэрээр хэд хэдэн удаа, эсвэл хязгааргүй удаа, эсвэл бүүр ганц ч удаа явж чадахгүй байж болно. Ингээд Инна-д хамгийн олон удаа явах эхлэл нүдийг олж өгнө үү.

Оролт

Оролтын эхний мөрөнд $n$, $m$ тоо ($1 ≤ n, m ≤ 10^3$) өгөгдөнө.

Дараагийн $n$ мөр бүрт хүснэгтийг илэрхийлэх $m$ тэмдэгт өгөгдөнө. Тэмдэгт бүр нь $D$, $I$, $M$, $A$-н аль нэг нь байна.

Хүснэгтэнд ядаж нэг $D$ үсэг байна.

Гаралт

Хэрвээ Инна ганц ч удаа Димагийн нэрээр явж чадахгүй бол "Poor Dima!" гэж хашилтгүй хэвлэнэ. Хэрвээ хязгааргүй удаа явж чадахаар бол "Poor Inna!" гэж хашилтгүйгээр хэвлэ. Хэрэв тодорхой тоогоор явж чадах бол хамгийн их тоог нь хэвлээрэй.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
1 2
DI
Гаралт
Poor Dima!
Оролт
2 2
MA
ID
Гаралт
Poor Inna!
Оролт
5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID
Гаралт
4

Тэмдэглэл

Notes to the samples:

In the first test sample, Inna cannot go through name DIMA a single time.

In the second test sample, Inna can go through the infinite number of words DIMA. For that, she should move in the clockwise direction starting from the lower right corner.

In the third test sample the best strategy is to start from the cell in the upper left corner of the table. Starting from this cell, Inna can go through name DIMA four times.

Сэтгэгдлүүдийг ачааллаж байна...