Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Quick Tortoise

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputJohn Doe has a field, which is a rectangular table of size *n* × *m*. We assume that the field rows are numbered from 1 to *n* from top to bottom, and the field columns are numbered from 1 to *m* from left to right. Then the cell of the field at the intersection of the *x*-th row and the *y*-th column has coordinates (*x*; *y*).

We know that some cells of John's field are painted white, and some are painted black. Also, John has a tortoise, which can move along the white cells of the field. The tortoise can get from a white cell with coordinates (*x*; *y*) into cell (*x* + 1; *y*) or (*x*; *y* + 1), if the corresponding cell is painted white. In other words, the turtle can move only along the white cells of the field to the right or down. The turtle can not go out of the bounds of the field.

In addition, John has *q* queries, each of them is characterized by four numbers *x*_{1}, *y*_{1}, *x*_{2}, *y*_{2} (*x*_{1} ≤ *x*_{2}, *y*_{1} ≤ *y*_{2}). For each query John wants to know whether the tortoise can start from the point with coordinates (*x*_{1}; *y*_{1}), and reach the point with coordinates (*x*_{2}; *y*_{2}), moving only along the white squares of the field.

Input

The first line contains two space-separated integers *n* and *m* (1 ≤ *n*, *m* ≤ 500) — the field sizes.

Each of the next *n* lines contains *m* characters "#" and ".": the *j*-th character of the *i*-th line equals "#", if the cell (*i*; *j*) is painted black and ".", if it is painted white.

The next line contains integer *q* (1 ≤ *q* ≤ 6·10^{5}) — the number of queries. Next *q* lines contain four space-separated integers *x*_{1}, *y*_{1}, *x*_{2} and *y*_{2} (1 ≤ *x*_{1} ≤ *x*_{2} ≤ *n*, 1 ≤ *y*_{1} ≤ *y*_{2} ≤ *m*) — the coordinates of the starting and the finishing cells. It is guaranteed that cells (*x*_{1}; *y*_{1}) and (*x*_{2}; *y*_{2}) are white.

Output

For each of *q* queries print on a single line "Yes", if there is a way from cell (*x*_{1}; *y*_{1}) to cell (*x*_{2}; *y*_{2}), that meets the requirements, and "No" otherwise. Print the answers to the queries in the order, in which the queries are given in the input.

Examples

Input

3 3

...

.##

.#.

5

1 1 3 3

1 1 1 3

1 1 3 1

1 1 1 2

1 1 2 1

Output

No

Yes

Yes

Yes

Yes

Input

5 5

.....

.###.

.....

.###.

.....

5

1 1 5 5

1 1 1 5

1 1 3 4

2 1 2 5

1 1 2 5

Output

Yes

Yes

Yes

No

Yes

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:36:34 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|