Problem Description

You are given an $n\times n$ grid where each cell is either land or water. The rows and columns of the grid are numbered $1,2,\dots,n$. You can move in the grid by taking steps left, right, up or down. Two cells are connected if you can move between them in one or more steps, while staying on the same type of cell.

The land cells form one connected island and the water cells form one connected ocean. The first and last rows and columns contain only water cells.

Your task is to answer $q$ queries: given two land cells $(r_1,c_1)$ and $(r_2,c_2)$, what is the minimum number of steps needed to move from the first cell to the second one while staying on land?

Input Format

The first line contains two integers $n$ and $q$: the size of the grid and the number of queries.

The next $n$ lines each have $n$ characters describing the grid. "." is a water cell and "#" is a land cell.

The next $q$ lines each have four integers $r_1$, $c_1$, $r_2$ and $c_2$: the row and column of the first cell, followed by the row and column of the second cell.

Output Format

Print the answer to each query on separate lines.

8 4
........
..####..
.##.###.
.##.###.
.#......
.#####..
..#####.
........
2 3 3 7
4 5 4 5
4 7 7 7
6 2 3 2

5
0
17
3

Hint

Constraints

• $3\le n\le 1000$
• $1\le q\le 10^5$
• $1 < r_1,c_1,r_2,c_2 < n$ in all queries

Scoring