B21 实践-6 猪猪填海

题目描述

猪猪的海上世界是一个 $m\times n$ 的棋盘。 每个格子有一个值 $v$ ，表示海床的高度。 敬畏的猪猪们，想通过搬运沙石，填埋部分的海域，营造更多可用的生活环境。 已知猪猪们整队从土丘国出发，每只猪都可运送高度为 $d$ 的填充物，每次都有 $k^2$ 只猪一起飞行，组成一个 $k*k$ 的矩形移动。 当头猪飞到 $(x,y)$ 的位置，整个队伍会有序地将填充物释放到对应 $(x,y)->(x+k-1,y+k-1)$ 的海床内（超出地图部分，忽略不计）。 经过若干次的努力，海床将会发生变化，这个过程中，猪猪神会不定期地查询海床的整体变化，以检测整个生态的稳定性。

输入格式

共 $n+2$ 行： 第一行四个正整数 $n,m,k,d$ ，分别表示棋盘世界的列、行数，猪猪编队的规模，单猪携带的填充物高度 $d$； 接下来一个矩阵，数据表示海床的海拔； 接下来一行，一个整数 $t$： 接下来 $t$ 行，每行三个整数 $a,x,y$： 当 $a$ 为 $1$ ，表示一个编队的猪猪运输队到了，头猪会落在 $(x,y)$ 坐标； 当 $a$ 为 $2$ ，表示一个猪神来视察，他想知道 $(x,y)$ 坐标的海床高度。

输出格式

若干行，每行一个整数，表示当次猪神视察的海床的高度。

样例输入

3 3 2 3
0 0 0
0 0 0
0 0 0
3
1 1 1
1 2 2
2 2 2

样例输出

6

样例解释

#第一次：填充
3 3 0
3 3 0
0 0 0

#第二次：填充
3 3 0
3 6 3
0 3 3

#第三次：视察
3  3  0
3 (6) 3
0  3  3

地图状态如上所示，猪神查验的 $(2,2)$ 的海床高度为 $6$。

数据范围

对于 $30\%$ 的数据： $1 \le x,y \le n,m \le 100;1 \le d,t \le 100$ ; 对于 $100\%$ 的数据： $1 \le x,y \le n,m \le 1000;1 \le d \le 10^5$; $1 \le t \le 1000$, 其中$a$为$2$的数量不超过$100$次。