Description
Sebastian Domo is a Formula One racer. Now it's the last race in Abu Dhabi, he needs this win to get his first world championship.
During this race, he is leading the Grand Prix for 57 laps, there is one more lap to go. However, in the early part of the race, he got a 5-second penalty for causing a collision with others. He needs to finish his race faster than his competitors by at least 5 seconds to win the race.
There is an NxM grid representing the race circuit, where '.' is the track, 'X' is the wall, and '-' is the finish line.
You and your competitors can move on the map in 4 directions (up, left, down, right). Moving one step costs you 1 second. However, you can not move into a wall.
Given the race circuit and the start position of yours and your competitors, please find out whether Domo can win his first world championship, and the difference between your finish time and the fastest competitor's time.
Input
The first line consists of 3 integers N, M, and Q, representing the size of the race circuit, and the number of competitors.
(1 ≤ N, M ≤ 20, 1 ≤ Q ≤ 3)
For the next N lines, each line consists of M characters, representing the race circuit.
For the next Q+1 lines, each line consists of two numbers i and k, representing Domo's position and his competitors' position on which row and which column.
(0 ≤ i < N, 0 ≤ k < M)
During the racing, you don't need to worry about the fighting between Domo and his competitors (moving into the same grid), it won't affect their pace at all.
It's guaranteed that using recursion can solve this problem.
The aligned sample input
Output
Output the time Domo and his competitors need to finish the race at the first line, separated with whitespaces.
At the second line, output the finish time difference between Domo and the fastest competitor.
Remember to print a newline character at the end of each line.