\(n \times m\) өлшемді кесте берілген, ол '.' және '#' таңбаларынан тұрады. '.' — бос ұяшық, ал '#' — жабық (блокталған) ұяшық.

Тақ өлшемді квадратты қарастырамыз: \(1 \times 1\), \(3 \times 3\), \(5 \times 5\) және т.,с.,с. Әр квадраттың орталығы болады — дәл ортасындағы ұяшық.

Квадратты орталығы \((x,y)\) ұяшығында тұратындай етіп қоюға болады, егер ол толықтай кестенің ішінде орналасса және квадраттың ішінде '#' бар бірде-бір ұяшық болмаса (яғни, квадраттың барлық ұяшықтары '.').

Квадратты жылжытуға болады. Бір қадамда квадратты бір ұяшыққа жоғары, төмен, солға немесе оңға жылжытуға рұқсат етіледі (яғни, квадраттың орталығы көршілес ұяшыққа ауысады). Әр қадамнан кейін квадрат әлі де кестенің ішінде болуы керек және ешбір '#' ұяшығын қамтымауы тиіс.

\(q\) сұраныс берілген. Әр сұраныста екі ұяшық \((x_1,y_1)\) және \((x_2,y_2)\) беріледі. Бастапқыда квадраттың орталығы \((x_1,y_1)\) ұяшығында орналасқан. Квадратты жылжытып, оның орталығын \((x_2,y_2)\) ұяшығына жеткізу керек.

Әр сұраныс үшін мұны орындауға болатын квадраттың ең үлкен мүмкін өлшемін (яғни, қабырғасының ұзындығын) табыңыз. Егер бұл тіпті \(1 \times 1\) квадрат үшін де мүмкін болмаса, \(0\) шығарыңыз.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(m\) (\(1 \le n, m \le 1000\)) жазылған.

Келесі \(n\) жолда кесте жазылған — \(m\) символы '.' немесе '#'.

Келесі жолда бүтін сан \(q\) (\(1 \le q \le 3 \cdot 10^5\)) жазылған.

Келесі \(q\) жолда сұраныстар жазылған, төрт бүтін сан \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(1 \le x_1, x_2 \le n\), \(1 \le y_1, y_2 \le m\)). \((x_1,y_1)\) және \((x_2,y_2)\) ұяшықтарының бос екендігіне кепілдік беріледі (кестеде оларда '.' таңбасы тұр).

Шығару

Әрбір сұраныс үшін бір санды шығарыңыз — жауапты жеке жолда.

Бағалау жүйесі

Мәселе 6 қосымша тапсырмадан тұрады.

Мысалдар

Енгізу 1

7 7
.....#.
...#.#.
....#..
....###
....#..
#......
.......
5
2 5 5 2
2 5 3 6
2 2 6 3
2 2 6 6
1 1 7 7

Жауап 1

1
0
3
1
1