题目描述

Inna 和 Dima 在商店买了一张 $n \times m$ 的表格。表格的每个格子里写着单个字母："D"、"I"、"M"、"A"。

Inna 深爱 Dima，所以她想在表格上移动时尽可能多地走完他的名字。为此，Inna 这样行动：

1. 一开始，Inna 选一个写有字母 "D" 的格子；
2. 然后 Inna 可以走到一个四方向相邻且写着字母 "I" 的格子；再从那里走到一个相邻且写着 "M" 的格子；再走到一个相邻且写着 "A" 的格子。此时认为她走完了一遍名字；
3. Inna 的下一步可以走到相邻的 "D" 格子，继续按同样方式走名字 DIMA。Inna 从不跳过字母：从 "D" 永远走到 "I"，从 "I" 永远走到 "M"，从 "M" 永远走到 "A"，从 "A" 永远走到 "D"。

取决于初始格子的选择，Inna 可能可以无限次走完名字 DIMA，也可能只能走有限多次，甚至一次都走不了。请帮 Inna 求出她能走完名字 DIMA 的最大次数。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^3$）。

接下来 $n$ 行描述这张表格，每行 $m$ 个字符。每个字符是 "D"、"I"、"M"、"A" 之一。

注意：不保证表格中至少有一个字母 "D"。

输出格式

如果 Inna 一次也走不完名字 DIMA，输出一行 "Poor Dima!"（不含引号）；如果她可以无限次走完名字 DIMA，输出 "Poor Inna!"（不含引号）；否则输出一个整数——Inna 走完名字 DIMA 的最大次数。

1 2
DI

Poor Dima!

2 2
MA
ID

Poor Inna!

5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID

4

说明/提示

第一组样例中，Inna 一次也走不完名字 DIMA。

第二组样例中，Inna 可以无限次走完名字 DIMA：她只需从右下角开始沿顺时针方向走。

第三组样例中，最优策略是从表格左上角的格子出发。从这个格子出发，Inna 可以走完四次名字 DIMA。