Inna和Dima在店里买了一张n×m大小的桌子。表的每个单元格包含一个字母:“D”、“I”、“M”、“A”。
Inna 爱 Dima,所以她想在桌子上移动时尽可能多地重复他的名字。为此,Inna 的行为如下:
1. 最初,Inna 选择表格中写有字母“D”的某个单元格;
2. 然后 Inna 可以移动到某个包含字母“I”的侧面相邻的表格单元格;然后,她可以从该单元格转到包含书面字母“M”的侧面相邻表格单元格之一;然后她可以转到包含字母“A”的侧面相邻单元格。然后,伊娜认为她已经记下了她爱人的名字;
3. Inna 的下一步行动可以是转到包含字母“D”的侧面相邻表格单元格之一,然后以类似的方式继续遍历名称 DIMA。伊娜从不漏掉任何一个字母。因此,从字母“D”她总是转到字母“I”,从字母“I”她总是转到字母“M”,从字母“M”她总是转到字母“A”,从字母“A”她总是转到字母“D”。
根据初始表格单元格的选择,Inna 可以无限次或某个正的有限次数查看姓名 DIMA,或者她一次不能查看他的名字。帮助 Inna 找出她可以重复名字 DIMA 的最大次数。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 103)。
然后接下来的 n 行描述了 Inna 和 Dima 的桌子。每行包含 m 个字符。每个字符是以下四个字符之一:“D”、“I”、“M”、“A”。
请注意,不保证该表至少包含一个字母“D”。
输出
如果 Inna 无法一次输入名字 DIMA,则打印一行“Poor Dima!”没有引号。如果 DIMA Inna 可以输入无限多个名字,请打印“Poor Inna!”没有引号。否则打印一个整数——Inna 可以遍历名称 DIMA 的最大次数。
示例
输入 #1
1 2 DI
输出 #1
Poor Dima!
输入 #2
2 2 MA ID
输出 #2
Poor Inna!
输入 #3
5 5 DIMAD DIMAI DIMAM DDMAA AAMID
输出 #3
4
注意
样品注释:
在第一个测试样本中,Inna 无法单次访问名称 DIMA。
在第二个测试样本中,Inna 可以遍历无限多个单词 DIMA。为此,她应该从右下角开始按顺时针方向移动。
在第三个测试示例中,最佳策略是从表格左上角的单元格开始。从这个单元格开始,Inna 可以使用 DIMA 这个名字四次。