C. Инна и Дима
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Инна и Дима купили в магазине табличку размера n × m. В каждой ячейке этой таблички записана одна из букв: «D», «I», «M», «A».

Инна любит Диму, поэтому она хочет, двигаясь по табличке, собрать его имя как можно больше раз. Для этого Инна действует следующим образом:

  1. изначально Инна выбирает некоторую ячейку таблицы, в которой записана буква «D»;
  2. затем Инна может перейти в одну из соседних по стороне ячеек таблицы, в которой записана буква «I»; затем из этой ячейки она может перейти в одну из соседних по стороне ячеек таблицы, в которой записана буква «M»; затем в одну из соседних по стороне ячеек таблицы, в которой записана буква «A», после чего Инна считает, что собрала целиком имя своего возлюбленного;
  3. следующим ходом Инна может перейти в одну из соседних по стороне ячеек таблицы, в которой записана буква «D», и далее аналогичным образом продолжить набор имени DIMA. Инна никогда не пропускает буквы, то есть из буквы «D» она всегда переходит в букву «I», из буквы «I» — в букву «M», из буквы «M» — в букву «A», а из буквы «A» — в букву «D» для начала набора имени еще раз.

В зависимости от выбора первоначальной ячейки таблицы Инна может собрать слово DIMA либо бесконечное количество раз, либо некоторое положительное конечное количество раз, либо вообще не может собрать слово DIMA ни разу. Помогите Инне определить, какое максимальное количество раз она может собрать слово DIMA.

Входные данные

Первая строка входных данных содержит два целых числа n и m (1 ≤ n, m ≤ 103).

Далее следует n строк, описывающих таблицу Инны и Димы. Каждая строка содержит m символов. Каждый символ — это один из символов: «D», «I», «M», «A».

Обратите внимание, не гарантируется, что таблица содержит хотя бы одну букву «D».

Выходные данные

Если Инна не может собрать ни одного слова DIMA, в единственной строке выведите «Poor Dima!» без кавычек. Если Инна может собрать бесконечное количество слов DIMA, выведите «Poor Inna!» без кавычек. Иначе выведите целое число — какое максимальное количество раз Инна сможет собрать слово DIMA.

Примеры
Входные данные
1 2
DI
Выходные данные
Poor Dima!
Входные данные
2 2
MA
ID
Выходные данные
Poor Inna!
Входные данные
5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID
Выходные данные
4
Примечание

Пояснения к примерам:

В первом тестовом примере, Инна не может собрать слово DIMA ни разу.

Во втором тестовом примере, Инна может собрать бесконечное количество слов DIMA. Для этого она должна двигаться по часовой стрелке, начиная от правого нижнего угла.

В третьем тестовом примере, выгоднее всего изначально выбрать ячейку в левом верхнем углу таблицы. Начиная от этой ячейки, можно собрать слово DIMA 4 раза.