Problem Description
When SuSu and his friends visited GanQuan village , something dangerous happened on them . They were trapped in a mysterious cave , what was worse ,there was a terrible monster lived in the cave , so they had to escape from the cave as quickly as possible .
But little monsters were also in the cave, as a result ,when SuSu was seen by the little monsters ,they would notice their boss to catch SuSu back.
Little monsters' visual field is showed in figure A. The grid colored red represents where the monster stands, the arrow represents which direction the monster walk to ,and the grids colored blue and red represents where the very monster can see at this moment. The monsters often walks in a straight line, and when they faces a wall or the boundary of the maze in front of him, they will cost 1 seconds to turn back, and then walk back along the straight line, until reach a wall again.
If SuSu was seen by the monsters ,it's impossible for them to escape from the cave . SuSu needs your help , please tell him the minimum time he needs to walk from the start point to the exit of the cave , be careful not to be seen by the monsters. Every seconds SuSu can move upward downward leftward and rightward , and can also make no movement.
Figure A
Input
The first line of input gives the number of cases, T (at most 90).
the first line of each case has four numbers n,m. (2<=n,m<=50)
then n lines with m characters describe the maze
'A' represents the init position of SuSu.
'B' represents the exit position of the cave.
'.' represents the grids can be walked on.
'*' represents the wall which can not be stepped on.
Then follows a number k (at most 50).
Next k lines with three integers x , y , d (1 <= x <= n,1 <= y <= m,1 <= d <= 4).represents a monster walking to d direction is in (x,y) positon (the top-left grid is (1,1) ) at 0 seconds .
The monster walks up when d == 1. walk down when d == 2.walk left when d == 3.walk right when d == 4.
Output
If SuSu can get to the exit in 1000 seconds ,output the minimum time he need. print "胜败兵家事不期 卷土重来是大侠" otherwise.
Following the case number (start with 1).
Sample Input
1
3 4
..
.A.B
***.
1
3 4 1
Sample Output
Case 1: 2
