온풍기 안녕!

유난히 추운 겨울이 예상되어 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 시험하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타내고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력으로 각 칸 (r, c)의 온도를 실시간으로 감시하는 시스템을 만들었다. (r, c)는 r행 c열을 뜻한다.

구사과의 성능 시험은 다음 작업을 순서대로 수행하며, 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 뜻한다.

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
2. 온도가 조절됨
3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
4. 초콜릿을 하나 먹는다.
5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K 이상이면 시험을 멈추고, 아니면 1부터 다시 시작한다.

집에 있는 모든 온풍기에서 바람이 한 번 나오는 과정은 다음과 같다.

<그림 1>

<그림 1>은 크기가 7×8인 집에 온풍기가 (3, 1)에 설치된 상황이다. 온풍기에는 바람이 나오는 방향이 있고, 그 방향은 오른쪽, 왼쪽, 위, 아래 중 하나다. 온풍기에서 따뜻한 바람이 한 번 나오면 다음 영역의 온도가 칸에 적힌 값만큼 올라간다. 아래 그림은 오른쪽 방향으로 바람이 나온 예시이며, 온풍기에서 바람이 나오는 방향에 따라 <그림 2>를 회전시켜서 그 방향으로 바람이 나왔을 때 올라가는 온도를 구할 수 있다.

<그림 2>

온풍기에서 바람이 한 번 나왔을 때, 온풍기의 바람이 나오는 방향에 있는 칸은 항상 온도가 5도 올라간다. 그 다음 이 바람은 계속 다른 칸으로 이동하며 다른 칸의 온도를 위의 그림과 같이 올린다. 어떤 칸 (x, y)에 온풍기 바람이 도착해 온도가 k (> 1)만큼 올라갔다면, (x-1, y+1), (x, y+1), (x+1, y+1)의 온도도 k-1만큼 올라간다. 이때 그 칸이 존재하지 않으면 바람은 이동하지 않는다. 온풍기에서 바람이 한 번 나왔을 때, 어떤 칸에 같은 온풍기에서 나온 바람이 여러 번 도착해도 온도는 여러 번 올라가지 않는다.

<그림 1>의 상태에서 온풍기 바람이 한 번 불었다면, 올라가는 온도의 양은 <그림 3>과 같다.

<그림 3>

일부 칸과 칸 사이에는 벽이 있어 온풍기 바람이 지나갈 수 없다. 바람이 오른쪽으로 불었을 때 어떤 칸 (x, y)에서 (x-1, y+1)로 바람이 이동하려면, (x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y+1) 사이에도 벽이 없어야 한다. (x, y)에서 (x, y+1)로 바람이 이동하려면 (x, y)와 (x, y+1) 사이에 벽이 없어야 한다. 마지막으로 (x, y)에서 (x+1, y+1)로 바람이 이동하려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y+1) 사이에 벽이 없어야 한다.

예를 들어, (3, 4)와 (3, 5) 사이에 벽이 있으면 온풍기에서 바람이 한 번 나왔을 때 온도는 <그림 4>와 같이 올라간다. 벽은 빨간색으로 표시했다.

<그림 4>

(3, 5)는 (3, 4), (2, 4), (4, 4)에서 바람이 이동할 수 없기 때문에, 온도가 올라가지 않는다.

만약 바람의 방향이 왼쪽인 온풍기가 (4, 7)에 있고, (3, 4)와 (3, 5) 사이에 벽, (2, 5)와 (3, 5) 사이에 벽이 있으면 온풍기에서 바람이 한 번 나왔을 때 <그림 5>와 같이 온도가 올라간다. <그림 6>은 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, (4, 4)와 (4, 5) 사이, (4, 4)와 (5, 4) 사이, (4, 6)과 (5, 6) 사이에 벽이 있는 경우다.

<그림 5>	<그림 6>

구사과의 집에는 온풍기가 2대 이상 있을 수도 있다. 이 경우 각 온풍기가 올린 온도를 모두 합한 값이 그 칸이 올라간 온도다.

예를 들어, <그림 7>은 <그림 6>과 같은 벽을 가진 집에서 바람의 방향이 위인 온풍기가 (7, 5)에 있는 경우이고, <그림 8>은 <그림 6>과 같은 벽을 가진 집에서 바람의 방향이 아래인 온풍기가 (2, 5)에 있고 바람의 방향이 위인 온풍기가 (7, 5)에 있는 경우다. <그림 8>은 같은 벽을 가진 집에서 <그림 6>의 온풍기와 <그림 7>의 온풍기가 동시에 설치된 상황이므로, 각 칸이 올라간 온도는 두 그림의 값을 더한 값과 같다. 온풍기가 있는 칸도 다른 온풍기 때문에 온도가 올라갈 수 있으므로, <그림 8>에서 온풍기의 위치는 표시하지 않았다.

<그림 7>	<그림 8>

온도가 조절되는 과정은 다음과 같다.

모든 인접한 칸에 대해서, 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋만큼 온도가 조절된다. 온도가 높은 칸은 이 값만큼 온도가 감소하고, 낮은 칸은 온도가 올라간다. 인접한 두 칸 사이에 벽이 있으면 온도가 조절되지 않는다. 이 과정은 모든 칸에 대해서 동시에 일어난다.

다음은 온도 조절의 예시다.

(1, 1)에서 (1, 2)와 (1, 3)으로 공기가 섞인다.

(2, 2)와 (3, 2) 사이에 벽이 있기 때문에, (3, 2)는 온도가 그대로 유지된다.

모든 칸에 대해서 동시에 온도의 조절이 일어난다.

가장 바깥쪽 칸은 1행, R행, 1열, C열에 있는 칸이다. 예를 들어, <그림 9>와 같은 경우 가장 바깥쪽 칸의 온도가 1씩 감소하면 <그림 10>과 같이 된다. 온도가 0인 칸은 온도가 감소하지 않는다.

<그림 9>	<그림 10>

방의 크기와 방에 설치된 온풍기의 정보, 벽의 위치와 조사하려고 하는 칸의 위치가 주어진다. 구사과가 먹은 초콜릿의 개수를 출력한다.

첫째 줄에 세 정수 R, C, K가 주어진다. 둘째 줄부터 R개의 줄에 방의 정보가 주어진다. i번째 줄의 j번째 정수는 (i, j)의 정보를 뜻하며 다음 중 하나다.

• 0: 빈 칸
• 1: 방향이 오른쪽인 온풍기가 있음
• 2: 방향이 왼쪽인 온풍기가 있음
• 3: 방향이 위인 온풍기가 있음
• 4: 방향이 아래인 온풍기가 있음
• 5: 온도를 조사해야 하는 칸

다음 줄에는 벽의 개수 W가 주어진다. 다음 W개의 줄에는 벽의 정보가 주어지며, 이 정보는 세 정수 x, y, t로 이루어져 있다. t가 0인 경우 (x, y)와 (x-1, y) 사이에 벽이 있고, 1인 경우에는 (x, y)와 (x, y+1) 사이에 벽이 있다.

구사과가 먹는 초콜릿의 개수를 출력한다. 만약, 먹는 초콜릿의 개수가 100을 넘어가면 101을 출력한다.

• 2 ≤ R, C ≤ 20
• 1 ≤ K ≤ 1,000
• 온풍기는 하나 이상 있고, 온도를 조사해야 하는 칸도 하나 이상 있다.
• 0 ≤ W ≤ R×C
• 1 < x ≤ R, 1 ≤ y ≤ C (t = 0)
• 1 ≤ x ≤ R, 1 ≤ y < C (t = 1)
• 온풍기가 있는 칸과 바람이 나오는 방향에 있는 칸 사이에는 벽이 없다.
• 온풍기의 바람이 나오는 방향에 있는 칸은 항상 존재한다.
• 같은 벽이 두 번 이상 주어지는 경우는 없다.