题目描述 我们已经进入了互联网时代，许多软件应用已从单机版转变为在线应用，电脑游戏也在遵循这一趋势。在线游戏之所以越来越受欢迎，不仅因为它们更智能，还因为能带来巨大利润。《中国日报》2004 年报道称：“中国电脑游戏产业发展迅速，去年在线游戏收入达 13 亿元，预计到 2007 年将达到 67 亿元。”

然而，好游戏源于优秀的程序员。以一款角色扮演游戏（RPG）为例，老板要求你完成一些任务。为简化问题，假设游戏中有两种角色：玩家和怪物。你的任务是帮助玩家尽快到达宝藏位置并获取宝藏。 游戏地图 地图是一个 $N×M$ 的矩阵，每个单元格可能是可通行的空地$（.）$、不可通行的岩石（#）、玩家起点（p）、宝藏位置$（t）$、非攻击性怪物初始位置$（n）$或攻击性怪物初始位置$（a）$。同一时刻，最多有一个角色占据某个单元格。 玩家移动规则 时间初始为 $0$，玩家从起点出发，目标是到达宝藏位置。 每一秒内，玩家可以选择： 停留在当前单元格。 行走：移动到相邻的 $8$ 个方向的可通行单元格（如图 1），耗时 $1$ 秒。 奔跑：移动到斜对角 2 格远的可通行单元格（如图 2），但需满足中间单元格可通行（如图 3，若中间格是岩石则无法奔跑），耗时 $1$ 秒。 怪物规则 攻击性怪物（a）：玩家不能进入其所在单元格或周围 $8$ 个相邻单元格（攻击范围，如图 4）。 非攻击性怪物（n）：玩家不能进入其所在单元格，但可以经过其相邻单元格。 怪物移动：每个怪物按给定的位置序列循环移动。例如，怪物 $i$ 的位置序列为$(x1,y1), (x2,y2), ..., (xs,ys)$，则$t$ 时刻的位置为序列中第 $(t mod s)$ 个位置（从 0 开始计数）。 每回合开始时，所有怪物先移动。若玩家所在单元格被怪物占据，或攻击性怪物移动后使玩家处于其攻击范围，玩家死亡，任务失败。随后玩家移动，移动路径不能经过岩石、怪物占据的单元格或攻击性怪物的攻击范围。 输入 多组测试用例，每组以两个$0地图描述：$N$行$ M 列字符矩阵，包含#、.、p、t、n、a。 怪物信息：第 N+2$行给出怪物总数$p$，随后$p$ 行描述每个怪物的位置序列（按初始位置的行优先顺序编号）。 输出 输出玩家获取宝藏的最短时间（秒）。若无法在 $100$ 秒内到达，或不可能到达，输出 "impossible"。相邻测试用例的输出用空行分隔。 输入输出示例 输入数据 1：

plaintext 7 8
#.#####.
#.t#..p.
#..#....
..#a.#.#
#...##.n
.#......
........
2
2 4 4 5 4
3 5 8 6 8 5 7

3 3
p#.
##.
t..
0

2 2
#t
p#
0
0 0

输出数据 1：

plaintext 8
impossible
1

提示： 在第一个示例中，玩家按 (2,7)→(4,7)→停留→(6,7)→(7,6)→(7,4)→(5,2)→(3,2)→(2,3) 的路径移动，最短时间为 8 秒。