Инна и Дима купили в магазине табличку размера n × m. В каждой ячейке этой таблички записана одна из букв: «D», «I», «M», «A».
Инна любит Диму, поэтому она хочет, двигаясь по табличке, собрать его имя как можно больше раз. Для этого Инна действует следующим образом:
- изначально Инна выбирает некоторую ячейку таблицы, в которой записана буква «D»;
- затем Инна может перейти в одну из соседних по стороне ячеек таблицы, в которой записана буква «I»; затем из этой ячейки она может перейти в одну из соседних по стороне ячеек таблицы, в которой записана буква «M»; затем в одну из соседних по стороне ячеек таблицы, в которой записана буква «A», после чего Инна считает, что собрала целиком имя своего возлюбленного;
- следующим ходом Инна может перейти в одну из соседних по стороне ячеек таблицы, в которой записана буква «D», и далее аналогичным образом продолжить набор имени DIMA. Инна никогда не пропускает буквы, то есть из буквы «D» она всегда переходит в букву «I», из буквы «I» — в букву «M», из буквы «M» — в букву «A», а из буквы «A» — в букву «D» для начала набора имени еще раз.
В зависимости от выбора первоначальной ячейки таблицы Инна может собрать слово DIMA либо бесконечное количество раз, либо некоторое положительное конечное количество раз, либо вообще не может собрать слово DIMA ни разу. Помогите Инне определить, какое максимальное количество раз она может собрать слово DIMA.
Выходные данные
Если Инна не может собрать ни одного слова DIMA, в единственной строке выведите «Poor Dima!» без кавычек. Если Инна может собрать бесконечное количество слов DIMA, выведите «Poor Inna!» без кавычек. Иначе выведите целое число — какое максимальное количество раз Инна сможет собрать слово DIMA.
Примечание
Пояснения к примерам:
В первом тестовом примере, Инна не может собрать слово DIMA ни разу.
Во втором тестовом примере, Инна может собрать бесконечное количество слов DIMA. Для этого она должна двигаться по часовой стрелке, начиная от правого нижнего угла.
В третьем тестовом примере, выгоднее всего изначально выбрать ячейку в левом верхнем углу таблицы. Начиная от этой ячейки, можно собрать слово DIMA 4 раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
DI
|
Poor Dima!
|
|
2
|
2 2
MA
ID
|
Poor Inna!
|
|
3
|
5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID
|
4
|