lakshagruha-maze

Duryodhana and Shakuni plans to take down Pandvas. Duryodhana convinced his father Dhritarashtra to send Pandavas to Varnavrata. Dhritarashtra affectionately told the Pandavas to go there as the people to Varnavrata will also be very happy to receive the sons of Pandu. The unsuspecting Pandavas were easily persuaded. Duryodhana was elated and sent their trusted minister Purochana to Varnavrata with secret instructions.
Purochana began building a beautiful palace for the Pandavas at Vanravrata, however, the palace was built with the most combustible materials Jute, lac, oil and fat was used as the building materials for the palace. The palace was indeed being built very skilfully as it was in the form of a MAZE, which made the ecape from the palace very difficult. 
Duryodhana's set the palace on fire once everyone was settled in. Duryodhana being aware of strength and intelligence of Pandavas, thus released some extremely powerful Rakshasha in the palace to kill Pandavas in the palace itself. Pandavas are now trying to escape the maze, but must avoid the path of Rakshasha patrolling in the palace or they will die. Additionally, Pandavas needs to escape within a certain amount of time, as palace is made of very combustible material and will burned down completely in that time.
Your task is to determine if Pandavas can escape the maze, and if so the minimum time they will take. . There is a timer that keeps track of how long Pandavas have been in the maze. The timer starts at 0. Pandavas may move to one of the adjacent cells of the maze (north, east, south, or west of his current position), provided that cell is neither a wall nor lies in path of patrolling rakshasha. Pandavas also has the option of standing still. 
All rakhshasha move to the next cell in their respective patrol paths. If any rakshasha moves into the cell now occupied by Pandavas , Pandavas will die. Rakshasha’s patrol paths will be given as a list of waypoints. Each waypoint will be in-line either horizontally or vertically with the next waypoint in the list, and the final waypoint will similarly be in-line with the first waypoint. Rakshashas will move from waypoint to waypoint, one square at a time, using the shortest possible path. Once a Rakshasha reaches its final waypoint, it will travel back to the first waypoint and repeat the cycle.
For example, if a patrol path were given as the waypoints:
(2,1),(0,1),(0,0),(1,0),(1,3),(2,3)
Then the rakshasha's complete path would be:
(2,1),(1,1),(0,1),(0,0),(1,0),(1,1),(1,2),(1,3),(2,3),(2,2)
After which the sequence would repeat.
You will be given the layout of the maze, including Pandavas' starting position, the position of the exit, and path of the rakshashas.

Input:
Input will begin with T, the number of test cases. 
Each test case begins with 4 integers: M, N, C, and K, where M is the height of the maze, N is the width of the maze, C is the number of rakshashas patroling in palace, and K is the number of seconds before the palace will burn down completely. C lines follow, each describing the patrol path of a rakshasha. 
Each patrol path begins with an integer L, the number of waypoints in the path, followed by L pairs of integers giving the (x,y) coordinates of a waypoint on the path, where (0,0) is the top-left corner and (N-1, M-1) is the bottom-right corner. 
Finally, M lines of N characters each describe the maze itself. A '.' character indicates a passable square, and a 'X' character indicates an impassable wall (although the rakshasha's being magical creature may pass through walls). A 'P' character indicates the starting position of Pandavas (it is guaranteed that no Rakshasha will begin here), and a 'E' character indicates the exit
of the maze (there will be exactly one 'P' character and one 'E' character in each test case).  
Output:
For each test case, if Pandavas can escape Lakshagruha without dying , print the minimum number of seconds it will take them to escape.
Otherwise, print -1.
Constraints:
1 ≤ T ≤ 10 
1 ≤ M,N ≤ 30 
0 ≤ C ≤ 30 
0 ≤ K ≤ 100000
2 ≤ L ≤ 10 

SAMPLE INPUT
4
10 10 0 200
XX.E......
PX.XXXXXX.
.X...X..X.
.XXX....X.
....XXX.X.
X.X.....X.
....X.XXX.
.XXXX.X.X.
.X....X...
..........
3 10 1 18
2 1 1 7 1
XXX.XXXXXX
P........E
XXXXXX.XXX
5 5 2 13
2 2 4 2 1
3 4 2 3 2 2 2
XXPXX
XX.XX
E..XX
XXXXX
XXXXX
2 2 1 1000
2 1 1 1 0
PE
..

SAMPLE OUTPUT
22
18
-1
-1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: