Farmer John muốn bò giúp làm hồ. Vẽ đồng cỏ $R$ hàng ($3\le R\le100$), $C$ cột ($3\le C\le100$), ô sáu foot nhân sáu foot, độ cao trung bình inch ($10\le elev_{rc}\le5000$).

Huấn luyện “đào bằng giẫm”. Đàn khỏe phủ đúng $3\times3$, tới góc trên trái $R_s,C_s$ ($1\le R_s\le R-2;1\le C_s\le C-2$), hạ $D_s$ inch ($1\le D_s\le40$). Bò thấp chờ còn lại xuống bằng mình; không nhất thiết mọi ô giẫm, hoặc ô giẫm ít hơn.

Cho cao ban đầu, $N$ lệnh theo thứ tự ($1\le N\le20000$), mực nước $E$ ($0\le E\le5000$), thể tích inch khối không quá $2,000,000,000$. Mép có rào ngăn nước tràn.

Đồng cỏ $4\times6$, cao có hàng/cột:

Đồi trên phải $36$, nhỏ trên trái $28$, giữa hàng $4$ hơi lõm. Sau "$1\;4\;4$":

Chỉ ba ô thấp xuống, sáu nhóm chờ tới mức mình mà không xảy ra. Sau "$1\;1\;10$" trên trái:

Mực $22$ inch cho sâu:

Tổng sâu $66$ nhân diện tích sáu foot nhân sáu foot: $66\times72\times72=342,144$ inch khối, cạnh $72$ inch.

Viết chương trình tự động.

Dữ liệu vào

• Dòng $1$: $R,C,E,N$ cách dấu cách.

• Dòng $2,\ldots,R+1$: dòng $i+1$, hàng $i$ có $C$ nguyên cách dấu cách.

• Dòng $R+2,\ldots,R+N+1$: dòng $i+R+1$, lệnh $i$ có $R_s,C_s,D_s$.

Dữ liệu ra

• Dòng 1: nguyên, thể tích hồ mới bằng inch khối.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

342144

Ghi chú

Như ví dụ trong bài.

Tác giả: Rob Kolstad, 2008