---

Time Limit: 2 Seconds      

Memory Limit: 65536 KB

---

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.

Process to the end of the file.

Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

Sample Input

7 8 

#.#####. 

#.a#..r. 

#..#x... 

..#..#.# 

#...##.. 

.#...... 

........

Sample Output

13

这题是说Angle被人抓住了，她的朋友去救她。。而x是阻碍他的敌人，可是Angle的朋友足够强，能消灭全部敌人，可是在消灭敌人的同一时候，

他要多花费1秒的时间，题目要你求出他解救Angle所需的最短时间。。

这道题用BFS，但要注意的是最短路径也可能并非最优解。。

所以我们用定义一个二维数组来记录每一个位置时的最短时间，在BFS搜索的过程中，到某个位置时，搜索的结果大于最短时间时，不入队。

这样就攻克了本题的问题了。

此外，不要一推断到达目的位置时就推出BFS返回结果。。我就是由于在这里WA了一发。。由于这可能不是最优解。。仅仅有等到队列为空或

BFS搜索结束时，才干得出最优解或者是“无法到达目的位置”。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int maxn = 205;const int INF = 100000;//用于初始每一个位置的时间，尽可能开大点char map[maxn][maxn];//地图int mintime[maxn][maxn];//记录每一个位置的最小时间int n, m;//地图的大小int ax, ay;//Angel的位置int fx, fy;//Angel的friend的位置int ans;//结果//地图的走法int dx[] = { -1, 0, 0, 1 };int dy[] = { 0, -1, 1, 0 };struct point{ int x; int y;//方格的位置 int time;//记录当前走到这所花费的时间};queue
            
             Q;//队列int BFS()//BFS函数{ while( !Q.empty() ) { point temp = Q.front();//记录队首元素 Q.pop(); // if( temp.x==ax && temp.y==ay ) //return mintime[ax][ay]; 開始我在这输出，使得WA。。由于这可能不是最优解 for(int i=0; i<4; i++) { int xx = temp.x + dx[i]; int yy = temp.y + dy[i]; if( xx>=0 && xx
             
              =0 && yy