JOI-kun lives in IOI city. He knows that it gets very hot throughout the year in IOI city.

IOI city is a rectangular city of rectangular cells with with height **H** cells and width **W** cells. Of these cells, some are buildings, fields or walls. There are **P** buildings, numbered from 1 to **P**.

JOI-kun can travel to the buildings and fields of IOI city. JOI-kun can travel from any cell to its adjacent cells (in other words, the cells that share an edge with the current cell). However, JOI-kun may not leave IOI city.

JOI-kun must walk from building to building to complete a variety of errands. Although buildings have air-conditioning, fields do not. Since the sun is very strong, the fields are very hot and JOI-kun needs 1 unit of water to travel 1 cell in a field. Since there are no vending machines in fields, it is normal to carry a water bottle in IOI city. A water bottle of size **x** can contain at most **x** units of water. Since all buildings have a water supply, it is possible to refil water bottles at all buildings.

It is inconvenient to have to carry a big water bottle. JOI-kun wants to mimimize the size of the water bottle he has to carry while moving between buildings. Help JOI-kun determine the minimum size of the water bottle he has to carry in order to move between any pair of buildings.

You will be given a map of IOI city and **Q** queries. The **j**^{th} query (1 ≤ **j** ≤ **Q**) asks for the minimum size of the water bottle JOI-kun has to carry in order to move from building **S _{i}** to building

Read from standard input.

- The first line contains four integers
**H**,**W**,**P**and**Q**. This means IOI city has height**H**and width**W**and contains**P**buildings. There will be**Q**queries. - The next
**H**lines contain the map of IOI city. On the rth line (1 ≤**r**≤-**H**), there are**W**characters. The cth character (1 ≤**c**≤**W**) on each line represents the cell in IOI city that is at the rth row from the top and the cth column from the left. A '.' means that the cell is either a building or a field, and a '#' means that the cell is a wall. - On the
**j**^{th}line of the next**P**lines (1 ≤**j**≤**P**), there are 2 integers,**A**and_{j}**B**. This means that building_{j}**j**is at the cell on the**A**th row from the top and the_{j}**B**th column from the left. It is guaranteed that the cell is a '.' on the map given above._{j} - On the
**i**^{th}line of the next**Q**lines (1 ≤**i**≤**Q**), there are 2 integers,**S**and_{i}**T**. This means that the_{i}**i**^{th}query asks for the minimum size of the water bottle JOI-kun has to carry in order to move from building**S**to building_{i}**T**._{i}

Print **Q** lines to standard output.

On the **i**^{th} line (1 ≤ **i** ≤ **Q**), print the minimum size of the water bottle JOI-kun has to carry to move from building **S _{i}** to building

All test cases meet the following constraints.

- 1 ≤
**H**≤ 2 000. - 1 ≤
**W**≤ 2 000. - 2 ≤
**P**≤ 200 000. - 1 ≤
**Q**≤ 200 000. - 1 ≤
**A**≤_{j}**H**(1 ≤**j**≤**P**). - 1 ≤
**B**≤_{j}**W**(1 ≤**j**≤**P**). - (
**A**,_{i}**B**) ≠ (_{i}**A**,_{j}**B**) (1 ≤_{j}**i**<**j**≤**P**). - 1 ≤
**S**<_{i}**T**≤_{i}**P**(1 ≤**i**≤**Q**).

Subtask 1 (10 points):

The following constraints are met.

**H**≤ 200.**W**≤ 200.**P**≤ 200.

Subtask 2 (30 points):

The following constraints are met.

**P**≤ 5 000.**Q**= 1.

Subtask 3 (30 points):

The following constraints are met.

**P**≤ 5 000.**Q**≤ 10 000.

Subtask 4 (30 points):

No further constraints.

```
5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4
```

```
3
4
4
2
```

According to the input, the layout of IOI city is shown in the following grid. Black squares represent a wall and numbers represent the number of the building on the cell. Empty cells represent fields.

1 | ||||

◼ | ◼ | 4 | ||

◼ | 3 | |||

2 | ◼ | |||

For example, consider the path between buildings 2 and 4.

1 | ||||

◼ | ◼ | 4 | ||

◼ | 3 | · | ||

2 | ◼ | · | ||

· | · | · | · |

If you do not want to pass by other buildings, the minimum number of fields and thus the minimum size of the bottle needed to travel from building 2 to building 4 is 6.

1 | · | · | · | · |

· | ◼ | ◼ | 4 | |

· | ◼ | 3 | ||

· | 2 | ◼ | ||

However, we can instead move from building 2 to 1, passing by 3 fields, and then move from building 1 to 4, passing by 4 fields. Thus, since we can refil the water bottle at building 1, the minimum size of the water bottle JOI-kun needs is 4. No other path requires a smaller water bottle.

```
5 5 3 2
...#.
..#..
#....
.##..
...#.
1 3
5 2
1 5
1 2
1 3
```

```
-1
7
```

In this test case, there is no way to move from building 1 to building 2.

Subtask | Score |
---|---|

1 | 10 |

2 | 30 |

3 | 30 |

4 | 30 |

5 | 0 |