착한 말 나쁜 말

$N \times N$ 격자의 각 칸에 양파가 하나씩 심어져 있다. 각각의 양파에는 세균이 한 마리씩 살고 있는데, 이 세균들은 자주 모임을 연다. 이 격자에서 좌표 $(r, c)$는 $r$번째 행의 $c$번째 열에 있는 칸을 뜻한다. 각 세균에게는 두 가지 이동 방법이 있는데, 착한 말과 나쁜 말이다. 나쁜 말을 한 번 하면 $a$의 에너지가 소모된다. 착한 말을 하려면 지금 세균이 있는 칸이 착한 칸이어야 하며, $b$의 에너지가 소모된다. 현재 위치가 $(r, c)$라고 할 때 나쁜 말을 하면 화난 양파가 세균을 옆의 양파로 밀어내서 $|r' - r|+|c' - c| = 1$을 만족하는 $(r', c')$로 이동할 수 있으며, 착한 말을 하면 양파가 순간적으로 성장해서 세균을 높이 띄워주어 $\max(|r' - r|, |c' - c|) \le D$를 만족하는 $(r', c')$로 이동할 수 있다. 당연히 격자 밖으로 나가는 것은 불가능하다.

세균들이 계획한 $i$일의 모임 일정은 $(R_i, C_i)$에서 열리고, 이 날 태양 빛의 세기에 따라 $a = A_i$, $b = B_i$가 정해진다. 세균들이 각자 최소의 에너지를 사용하여 이동한다고 할 때, 모든 칸의 세균들이 모이기 위해 세균들이 사용해야 하는 총 에너지 합을 구해주자. 단, 양파는 한 번에 세균 하나씩만 이동시킬 수 있다고 한다. 모든 세균들은 모임이 끝난 뒤 자기가 사는 양파로 돌아가는데, 이 때는 에너지를 소모하지 않는다.

1번째 줄에 격자의 크기 $N$, 착한 말을 했을 때의 이동 범위 $D$, 모임 날짜의 수 $Q$가 공백으로 구분되어 주어진다.

$i + 1$번째 줄에는 길이 $N$의 문자열로 격자의 $i$번째 행의 상태가 주어진다. $j$번째 문자가 .일 경우 $(i, j)$는 나쁜 칸이며, #일 경우 착한 칸이다. ($1 \le i, j \le N$)

$i + N + 1$번째 줄에는 $i$일의 모임 일정에 대한 정보 $R_i$, $C_i$, $A_i$, $B_i$가 공백으로 구분되어 주어진다. ($1 \le i \le Q$)

$i$번째 줄에 $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$)