Problem C
One-Punch Wall

This tells a tale about Saitammar, a guy who wanders a maze for fun. The maze consists of $N$ rows and $M$ columns, where each cell is either an empty space or a wall. The rows are numbered from $1$ to $N$ top-to-bottom, and the columns are numbered from $1$ to $M$ left-to-right. A coordinate $(X,Y)$ represents a cell on row $X$ and column $Y$.

Let’s imagine $Q$ many scenarios. In the $i$-th scenario, Saitammar starts from coordinate $(A_ i,B_ i)$ and wants to get to the ending point at coordinate $(C_ i,D_ i)$. It is guaranteed that both the starting and ending point are always different empty spaces. Saitammar can move to his up, down, left, or right direction (by one cell) as long as it is another empty space. Note that Saitammar couldn’t move outside the maze. You are wondering if it is possible for Saitammar to reach the ending point from his starting point.

Additionally, here comes a surprise! Saitammar might actually, just for up to one time only, one-punch a wall! At any time during his movement, Saitammar could stop at one coordinate, and chooses a single cell of wall directly on his up, down, left, or right. Then, he one-punches that wall so the wall become an empty space; letting him to use that as a "shortcut" to reach the ending point! So, in the $i$-th scenario, you will also be given a value of $K_ i$. If $K_ i = 1$, then Saitammar could one-punch a wall for up to one time; otherwise, if $K_ i = 0$, Saitammar is hesitating and doesn’t want to one-punch any wall.

Your task is clear: for each scenario, please find out if Saitammar could reach the ending point, possibly using the one-punch wall!

Input

The first line contains three integers, $N$, $M$, and $Q$ $(1 \le N \times M \le 200\; 000$, $1 \le Q \le 100\; 000)$.

The next $N$ lines contain the maze, each consisting of $M$ characters of either ‘.’ which represents an empty space, or ‘#’ which represents a wall.

The next $Q$ lines contain the scenarios, each one on a separate line. Each scenario is given in the form of five integers, $A_ i (1 \le A_ i \le N)$, $B_ i (1 \le B_ i \le M)$, $C_ i (1 \le C_ i \le N)$, $D_ i (1 \le D_ i \le M)$, and $K_ i (0 \le K_ i \le 1)$. It is guaranteed that $A_ i \ne C_ i$ or $B_ i \ne D_ i$.

Output

For each scenario, print “yes” if it is possible for Saitammar to reach the ending point from his starting point (possibly using the one-punch wall if permitted), or “no” if it is not possible.

Subtasks

1. ($12$ Points): Only contains the following input:

                   5 7 4
                   .#.....
                   .######
                   .#.....
                   .###.##
                   .#.#.#.
                   1 1 5 5 1
                   5 3 1 3 0
                   3 1 5 7 1
                   5 1 3 1 0
           

2. ($16$ Points): $Q = 1$ and $N = 1$.

3. ($10$ Points): $N = 1$.

4. ($23$ Points): $Q = 1$ and $K_1 = 0$.

5. ($13$ Points): $K_ i = 0$ for all $1 \le i \le Q$.

6. ($8$ Points): $Q = 1$ and $N \times M \le 2000$.

7. ($8$ Points): $Q = 1$.

8. ($10$ Points): No additional constraints.

Explanation of Sample 1

The following is the illustration of the maze in sample 1.

In the first scenario, Saitammar starts at coordinate $(1,1)$ and wants to go to coordinate $(1,3)$. Saitammar can simply move to the right by $2$ cells as follows.

In the second scenario, Saitammar wants to go from $(1,2)$ to $(1,5)$. At best, Saitammar can only move right to $(1,3)$. Note that as $K_2 = 0$, Saitammar doesn’t want to one-punch a wall. It is practically impossible to go to $(1,5)$ without breaking any wall, specifically the one at $(1,4)$.

The third scenario is similar to the second scenario. However, as $K_3 = 1$, Saitammar can now one-punch a wall. Saitammar can first move right to $(1,3)$, one-punch the wall at $(1,4)$, then move to the right by $2$ cells to be at $(1,5)$.

The fourth scenario is the reverse version of the third scenario. Saitammar, which starts at $(1,5)$, can directly one-punch a wall at $(1,4)$ and then move to the left by $3$ cells to be at $(1,2)$.

In the fifth scenario, Saitammar wants to go from $(1,9)$ to $(1,5)$. Even if he can one-punch a wall, at best, Saitammar can only break the wall at $(1,7)$. Note that it is impossible to continue further to go to $(1,5)$ because of the wall at $(1,6)$.

Explanation of Sample 2

The following is the illustration of the maze and all scenarios in sample 2.

The upper-left image is the maze.

The upper-middle image illustrates both the first and second scenarios. In both scenarios, Saitammar can go from $(2,2)$ to $(4,4)$ without breaking any wall. Note that even if $K_2 = 1$, Saitammar is not required to one-punch any wall.

The upper-right image illustrates the third scenario where Saitammar cannot go to $(6,8)$ due to the walls.

The lower-left image illustrates the fourth scenario which is similar to the third. However, Saitammar is able to one-punch the wall at $(5,8)$ after positioning himself at $(4,8)$, allowing him to go to the ending point.

The lower-middle image illustrates the fifth scenario where Saitama can one-punch the wall at $(5,6)$ and use that as a shortcut to later go to $(2,6)$.

Lastly, the lower-right image illustrates the sixth scenario. Note that Saitammar cannot go to the ending point without one-punching a wall more than once.

1 9 5
...#.##..
1 1 1 3 0
1 2 1 5 0
1 2 1 5 1
1 5 1 2 1
1 9 1 5 1

yes
no
yes
yes
no

7 9 6
#########
#...#...#
#.#.###.#
#...#...#
####.####
#...#.#.#
#########
2 2 4 4 0
2 2 4 4 1
2 6 6 8 0
2 6 6 8 1
5 5 2 6 1
6 2 2 8 1

yes
yes
no
yes
yes
no