Good Word, Bad Word

An onion is planted in each cell of an $N \times N$ grid. Each onion is home to one bacterium, and these bacteria hold meetings often. In this grid, the coordinate $(r, c)$ denotes the cell in the $r$-th row and $c$-th column. Each bacterium has two ways to move: the good word and the bad word. Saying the bad word once consumes $a$ energy. To say the good word, the cell the bacterium is currently in must be a good cell, and saying it consumes $b$ energy. If the current position is $(r, c)$, saying the bad word makes the angry onion shove the bacterium to a neighboring onion, so the bacterium can move to any $(r', c')$ satisfying $|r' - r|+|c' - c| = 1$; saying the good word makes the onion grow instantly and toss the bacterium high, so the bacterium can move to any $(r', c')$ satisfying $\max(|r' - r|, |c' - c|) \le D$. Moving outside the grid is of course impossible.

The meeting scheduled for day $i$ is held at $(R_i, C_i)$, and the day's sunlight intensity determines $a = A_i$ and $b = B_i$. Assuming each bacterium moves using the minimum energy, find the total energy the bacteria must spend for all bacteria in the grid to gather. The onions can move only one bacterium at a time. After the meeting ends, every bacterium returns to the onion it lives in, and this costs no energy.

The first line gives the grid size $N$, the movement range $D$ of the good word, and the number of meeting days $Q$, separated by spaces.

Line $i + 1$ gives the state of row $i$ of the grid as a string of length $N$. If the $j$-th character is ., then $(i, j)$ is a bad cell; if it is #, it is a good cell. ($1 \le i, j \le N$)

Line $i + N + 1$ gives the information for the meeting on day $i$: $R_i$, $C_i$, $A_i$, $B_i$, separated by spaces. ($1 \le i \le Q$)

On line $i$, print the total energy the bacteria must spend at the meeting on day $i$. ($1 \le i \le Q$)

• $1 \le D \le N \le 500$
• $1 \le Q \le 5$
• $1 \le R_i, C_i \le N$ ($1 \le i \le Q$)
• $1 \le A_i, B_i \le 10^9$ ($1 \le i \le Q$)