However, you quickly realize that Mr. Sidhu can't walk through walls! Therefore, you must now somehow include these obstacles into your program. The input will include a grid that will consist of O (representing an empty space) and X (representing an obstacle or otherwise unavailable space). You should note that each grid space is equal to one metre in length. It is guaranteed that the starting and destination points will be available (O, that is) and that the Main Office can be reached by walking.

What he does not know, however, is that the school's former physics teacher installed invisible teleportation devices over the summer to provide a more efficient means for teachers to move around. She also configured it such that it would only work for Mr. Sidhu and no one else.

Unfortunately, she forgot about the devices — and she retired. As Mr. Sidhu walks down the hall, he is instantly teleported to the Main Office, his destination. Since he doesn't particularly enjoy being randomly teleported, he contacted the teacher and convinced her to remove the devices.

Being the curious student you are, you happened to stumble over a copy of the map of the teleportation devices on the teacher's desk of the classroom you have physics in, which contains the exact location of the devices as well as mentions that it would only affect Mr. Sidhu.

Since you are also a very compassionate student, you decide to show him the map but are disappointed when he tells you that the devices no longer exist. Therefore, to make him regret his decision, you decide to write a program that calculates exactly how much time Mr. Sidhu could have saved had he known the exact locations of the devices.

Input Specification

The first line of input will consist of the number of rows and columns ~R, C~ ~(1 \le R, C \le 1000)~, separated by one space. The next line represents his starting point and the following line is the Main Office. Note that rows and columns in this problem are zero-indexed. This is followed by ~R~ lines containing the grid as described above.

The next line of input will be ~T~ ~(0 \le T \le R \times C)~, the number of teleportation devices. This will be followed by ~T~ lines, consisting of two positive integers each separated by one space representing the coordinates of that device, the former being the row number and the latter the column number. You can assume that teleportation devices will not be on walls.

Output Specification

Your output should be the time he could have gained, in seconds.

Sample Input

5 5
4 4
1 2
OOXOO
OXOXO
OOOXX
XOXOX
OOOOO
1
3 3

Sample Output

5

Explanation for Sample Output

There is one device at 3, 3. He starts at 4, 4, the bottom-right of the grid. The length of the shortest path ignoring (walking over the tile) the device is 7 metres. Walking at 1 m/s means it will take him 7 seconds. But a teleportation device is only 2 metres away, thus allowing him to complete his journey in 2 seconds. The output should be 5, as he would have saved 5 seconds.