Robot Race

A robot race on a maze will be held in Byteland. The maze has the shape of a rectangle and is divided into $n \times m$ fields arranged in $n$ rows and $m$ columns. Each field is either empty or contains an obstacle.

The contestants register their robots for the competition and come to the maze one after another. Each contestant gets random coordinates of the initial field and the target field. The robot is then placed in the initial field and must get to the target field using a sequence of steps.

To make the game more challenging, the rules specify that in each step the robot can only move one field right or one field down in the maze. Moving the robot in any other direction is not allowed.

The contestant whose robot gets fastest from the initial field to the target field wins the competition. If the robot does not get to the target field in the time limit, the contestant is disqualified.

The organizers of the competition realized that if a contestant gets bad coordinates, the robot will not be able to get to the target field using any sequence of moves. In that case they would like to give the contestant another pair of coordinates.

You are given a map of a maze of size $n \times m$ and $q$ pairs of coordinates of the initial and target fields. Determine for each pair of coordinates whether it is possible to get from the initial field to the target field using a sequence of steps right or down.

The first line contains three integers $n$, $m$ and $q$: the number of rows of the maze, the number of columns of the maze and the number of pairs of coordinates.

Each of the following $n$ lines contains $m$ characters describing the fields of the maze. The character . represents an empty field and the character # a field with an obstacle.

Then $q$ lines follow describing the pairs of coordinates. The $i$-th of them contains four integers $r_{1,i}$, $c_{1,i}$, $r_{2,i}$, $c_{2,i}$: the row and the column of the initial field and the row and the column of the target field.

• It holds $1 \leq n, m \leq 1000$ and $1 \leq q \leq 10^6$.
• For all $i \in \{1, 2, \ldots, q\}$ it holds $1 \leq r_{1,i}, r_{2,i} \leq n$ and $1 \leq c_{1,i}, c_{2,i} \leq m$.
• For all $i \in \{1, 2, \ldots, q\}$ the fields in the maze with coordinates $(r_{1,i}, c_{1,i})$ and $(r_{2,i}, c_{2,i})$ are empty.
• In 20% of the test cases $q \leq 300$.

Output $q$ lines. The $i$-th line should contain the word YES if the robot can get from the $i$-th initial field to the $i$-th target field, or the word NO otherwise.