Problem C
OnePunch 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$ toptobottom, and the columns are numbered from $1$ to $M$ lefttoright. 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, onepunch 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 onepunches 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 onepunch a wall for up to one time; otherwise, if $K_ i = 0$, Saitammar is hesitating and doesn’t want to onepunch any wall.
Your task is clear: for each scenario, please find out if Saitammar could reach the ending point, possibly using the onepunch 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 onepunch wall if permitted), or “no” if it is not possible.
Subtasks

($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

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

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

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

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

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

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

($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 onepunch 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 onepunch a wall. Saitammar can first move right to $(1,3)$, onepunch 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 onepunch 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 onepunch 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 upperleft image is the maze.
The uppermiddle 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 onepunch any wall.
The upperright image illustrates the third scenario where Saitammar cannot go to $(6,8)$ due to the walls.
The lowerleft image illustrates the fourth scenario which is similar to the third. However, Saitammar is able to onepunch the wall at $(5,8)$ after positioning himself at $(4,8)$, allowing him to go to the ending point.
The lowermiddle image illustrates the fifth scenario where Saitama can onepunch the wall at $(5,6)$ and use that as a shortcut to later go to $(2,6)$.
Lastly, the lowerright image illustrates the sixth scenario. Note that Saitammar cannot go to the ending point without onepunching a wall more than once.
Sample Input 1  Sample Output 1 

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 
Sample Input 2  Sample Output 2 

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 