Farmer John은 소와 호수를 만들려 한다. 목장을 $R$행 ($3\le R\le100$), $C$열 ($3\le C\le100$)의 6피트 곱하기6피트 칸으로 나누고 평균 높이를 인치로 측정했다 ($10\le elev_{rc}\le5000$).
“밟아 파기” 훈련한 강한 무리가 정확히 $3\times3$칸을 덮고 좌상단 $R_s,C_s$ ($1\le R_s\le R-2;1\le C_s\le C-2$)로 가 $D_s$인치 ($1\le D_s\le40$) 낮춘다. 낮은 소는 다른 소가 높이까지 내려올 때까지 안 밟으므로 전부 밟거나 똑같이 낮추지 않을 수 있다.
초기 높이, 순서 있는 $N$ 지시 ($1\le N\le20000$), 수위 $E$ ($0\le E\le5000$)로 세제곱인치 물 부피를 구하라. 답은 $2,000,000,000$ 이하이며 경계 장벽으로 물이 넘치지 않는다.
$4\times6$ 목장 초기 높이, 행/열 번호:
| 행/열 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $1$ | $28$ | $25$ | $20$ | $32$ | $34$ | $36$ |
| $2$ | $27$ | $25$ | $20$ | $20$ | $30$ | $34$ |
| $3$ | $24$ | $20$ | $20$ | $20$ | $20$ | $30$ |
| $4$ | $20$ | $20$ | $14$ | $14$ | $20$ | $20$ |
우상단 언덕 $36$, 좌상단 작은 언덕 $28$, 행 $4$ 중간 살짝 낮다. "$1\;4\;4$" 뒤:
| 행 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $1$ | $28$ | $25$ | $20$ | $32$ | $32$ | $32$ |
| $2$ | $27$ | $25$ | $20$ | $20$ | $30$ | $32$ |
| $3$ | $24$ | $20$ | $20$ | $20$ | $20$ | $30$ |
| $4$ | $20$ | $20$ | $14$ | $14$ | $20$ | $20$ |
세 칸만 낮아지고 여섯 무리는 자기 높이까지 내려오길 기다렸지만 오지 않았다. "$1\;1\;10$"으로 좌상단 밟은 뒤:
| 행 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $1$ | $18$ | $18$ | $18$ | $32$ | $32$ | $32$ |
| $2$ | $18$ | $18$ | $18$ | $20$ | $30$ | $32$ |
| $3$ | $18$ | $18$ | $18$ | $20$ | $20$ | $30$ |
| $4$ | $20$ | $20$ | $14$ | $14$ | $20$ | $20$ |
수위 $22$인치일 때 깊이:
| 행 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $1$ | $4$ | $4$ | $4$ | -- | -- | -- |
| $2$ | $4$ | $4$ | $4$ | $2$ | -- | -- |
| $3$ | $4$ | $4$ | $4$ | $2$ | $2$ | -- |
| $4$ | $2$ | $2$ | $8$ | $8$ | $2$ | $2$ |
깊이 합 $66$에 6피트 곱하기6피트 면적을 곱하면 $66\times72\times72=342,144$ 세제곱인치, 변은 $72$인치.
계산 자동화 프로그램을 작성하라.
입력
줄 $1$: 공백 구분 $R,C,E,N$.
줄 $2,\ldots,R+1$: 줄 $i+1$은 행 $i$의 $C$ 정수, 공백 구분.
줄 $R+2,\ldots,R+N+1$: 줄 $i+R+1$은 지시 $i$의 $R_s,C_s,D_s$.
출력
예제
입력 1
4 6 22 2
28 25 20 32 34 36
27 25 20 20 30 34
24 20 20 20 20 30
20 20 14 14 20 20
1 4 4
1 1 10
출력 1
342144
참고
본문 예시와 같다.
문제 출제: Rob Kolstad, 2008