18375번 - 착한 말 나쁜 말

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

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

i번째 줄에 i일의 모임 일정에서 세균들이 사용해야 하는 총 에너지 합을 출력한다. (1 ≤ i ≤ Q)

• 1 ≤ D ≤ N ≤ 500
• 1 ≤ Q ≤ 5
• 1 ≤ R_i, C_i ≤ N (1 ≤ i ≤ Q)
• 1 ≤ A_i, B_i ≤ 10⁹ (1 ≤ i ≤ Q)