Minimum Time for All Travelers to Reach Their Destinations

You are given a grid of size R x C where each cell is either passable (denoted by '.') or blocked by an obstacle (denoted by '#'). There are T travelers, and each traveler has a starting position and a destination on the grid. Two cells are adjacent if they share a side (up, down, left or right).

Your task is to determine the minimum time required for all travelers to reach their destinations. Since each traveler moves concurrently, the answer is the maximum shortest path among all travelers. Formally, if d_i is the shortest distance from the start to the destination for traveler i, then the answer is given by

$$\min\; t \quad\text{such that} \quad t \ge \max_{1 \le i \le T} d_i.$$

If any traveler cannot reach their destination (i.e. the corresponding shortest path does not exist), output -1.

inputFormat

The input is read from standard input and has the following format:

R C
row_1
row_2
...
row_R
T
s1 r1 d1 c1
s2 r2 d2 c2
...
sT rT dT cT

Here, the first line contains two integers R and C — the number of rows and columns of the grid. The following R lines each contain a string of length C representing a row of the grid. Next, a single integer T denotes the number of travelers. Finally, the next T lines each contain four integers: the starting row, starting column, destination row, and destination column of a traveler (0-indexed).

outputFormat

Print a single integer to standard output: the minimum time required for all travelers to reach their destinations, or -1 if at least one traveler cannot reach their destination.

## sample

5 5
.#...
.....
.....
.....
...#.
3
0 0 4 4
1 1 2 2
3 0 0 4

8

</p>